题目来源

力扣每日一题；题序：1483

我的题解

方法一 哈希表 超内存

使用一个哈希表存储每个节点的祖先节点。

时间复杂度：O(n)
空间复杂度：O($n^2$)

class TreeAncestor {Map<Integer,List<Integer>> res;int[] parent;int n;public TreeAncestor(int n, int[] parent) {this.n=n;this.parent=parent;res=new HashMap<>();computedAncestor(n,parent);}private void computedAncestor(int n,int[] parent){for(int i=1;i<n;i++){List<Integer> l=res.getOrDefault(i,new ArrayList<>());l.add(parent[i]);l.addAll(res.getOrDefault(parent[i],new ArrayList<>()));res.put(i,l);}}public int getKthAncestor(int node, int k) {List<Integer> t=res.getOrDefault(node,new ArrayList<>());return k<=t.size()?t.get(k-1):-1;// while(parent[node]!=-1){//     k--;//     node=parent[node];// }// return k!=-1?node:-1;}
}

方法二 树上倍增

倍增的思路类似于动态规划，定义 ancestors[i][j] 表示节点 i 的第$2^j$个祖先。此题中，树最多有 50000 个节点，因此 ancestors 的第二维度的最大值可以设为 16。根据定义，ancestors[i][0]=parent[i]。状态转移方程是 ancestors[i][j]=ancestors[ancestors[i][j−1]][j−1]，即当前节点的第$2^j$个祖先，是他的第$2^{j-1}$ 个祖先的第 $2^{j-1}$ 个祖先。当第$2^j$ 个祖先不存在时，记为 −1。
查询时，需要将 k 的二进制表示从最低位到最高位依次进行判断，如果第 j 位为 1，则节点 node 需要进行转移到 ancestors[node][j]，表示 node 向祖先方向移动了$2^j$ 次。直至遍历完 k所有位或者 node 变为 −1。

时间复杂度：O(nlogn)
空间复杂度：O(nlogn)

class TreeAncestor {static final int LOG = 16;int[][] ancestors;public TreeAncestor(int n, int[] parent) {ancestors = new int[n][LOG];for (int i = 0; i < n; i++) {Arrays.fill(ancestors[i], -1);}for (int i = 0; i < n; i++) {ancestors[i][0] = parent[i];}for (int j = 1; j < LOG; j++) {for (int i = 0; i < n; i++) {if (ancestors[i][j - 1] != -1) {ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];}}}            }public int getKthAncestor(int node, int k) {for (int j = 0; j < LOG; j++) {if (((k >> j) & 1) != 0) {node = ancestors[node][j];if (node == -1) {return -1;}}}return node;}
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~