树节点的第 K 个祖先
难度:
标签:
题目描述
给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
实现 TreeAncestor 类：
TreeAncestor（int n， int[] parent）对树和父数组中的节点数初始化对象。getKthAncestor(int node, int k)返回节点node的第k个祖先节点。如果不存在这样的祖先节点，返回-1。
示例 1：
输入： ["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"] [[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]] 输出： [null,1,0,-1] 解释： TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]); treeAncestor.getKthAncestor(3, 1); // 返回 1 ，它是 3 的父节点 treeAncestor.getKthAncestor(5, 2); // 返回 0 ，它是 5 的祖父节点 treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点
提示：
1 <= k <= n <= 5 * 104parent[0] == -1表示编号为0的节点是根节点。- 对于所有的
0 < i < n，0 <= parent[i] < n总成立 0 <= node < n- 至多查询
5 * 104次
代码结果
运行时间: 415 ms, 内存: 44.4 MB
/*
* 思路：
* 使用 Stream API 的优势在于可以更直观地处理数组和集合操作。
* 不过由于祖先节点查询涉及较复杂的逻辑，纯粹的流操作可能并不适用。
* 我们仍然需要通过二进制提升法来构建 jump table。
*/
import java.util.stream.IntStream;
class TreeAncestor {
private int[][] jump;
private int maxPow;
public TreeAncestor(int n, int[] parent) {
maxPow = (int) (Math.log(n) / Math.log(2)) + 1;
jump = new int[n][maxPow];
IntStream.range(0, n).forEach(i -> jump[i][0] = parent[i]);
for (int j = 1; j < maxPow; j++) {
IntStream.range(0, n).forEach(i -> {
if (jump[i][j - 1] != -1) {
jump[i][j] = jump[jump[i][j - 1]][j - 1];
} else {
jump[i][j] = -1;
}
});
}
}
public int getKthAncestor(int node, int k) {
for (int j = 0; j < maxPow; j++) {
if ((k & (1 << j)) != 0) {
node = jump[node][j];
if (node == -1) return -1;
}
}
return node;
}
}解释
方法:
该题解采用了二进制倍增的思想来快速查找树节点的第k个祖先。在初始化时，我们首先计算每个节点的1代祖先（即直接父节点），然后依次计算每个节点的2的幂次代祖先，即2代、4代、8代等。这样，在查询第k个祖先时，我们可以利用k的二进制表示来快速定位需要跳跃的祖先节点。
时间复杂度:
初始化：O(nlog(n)), 查询：O(log(k))
空间复杂度:
O(nlog(n))
代码细节讲解
🦆
在初始化过程中，当你检查标记`flag`是否有非根节点的祖先时，具体是基于什么条件来判断的？
▷🦆
如果在某一层中所有节点都已经是根节点，为什么此时停止进一步计算祖先节点？
▷🦆
你如何处理节点编号超出范围的情况，比如在`p[u] = prev[prev[u]]`中如果`prev[u]`已经是-1，是否有进一步的检查机制？
▷🦆
在`getKthAncestor`方法中，如何确定需要跳跃的层数，特别是如何通过二进制表示确定这一点？
▷