lc 1483 树节点的第 K 个祖先
- 我们定义:节点的第 i 级父节点为第
个父节点 - 规律1:节点的第 n 个父节点 = 节点的第
个父节点的第 个父节点,其中 。- (倍增)以二进制为基础,节点 i 的 第
个父节点 = 节点 i 的第 个父节点的第 个父节点,即 (动态规划) - if (((k >> j) & 1) != 0) // 判断第 j 位是否为 1
- 若是1
- 有父节点 -> 往第 j 级父节点向上
- 没有父节点 -> 原题无解
- 若不是1,continued;
- 若是1
- (倍增)以二进制为基础,节点 i 的 第
// 题解参考leetcode官方题解,gpt生成注释
class TreeAncestor {
static final int LOG = 16; // 定义常量 LOG,表示每个节点的祖先个数上限。
// 此题中,树最多有 50000 个节点,因此 ancestors的第二维度的最大值可以设为 16。
int[][] ancestors; // 定义二维数组 ancestors,用于存储每个节点的祖先信息
// 构造函数,初始化祖先数组
public TreeAncestor(int n, int[] parent) {
ancestors = new int[n][LOG]; // 初始化二维数组大小为 n * LOG
for (int i = 0; i < n; i++) {
Arrays.fill(ancestors[i], -1); // 将二维数组每个元素初始化为 -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) { // 如果当前节点存在第 j - 1 级祖先
ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1]; // 则当前节点的第 j 级祖先为其第 j - 1 级祖先的第 j - 1 级祖先
}
}
}
}
// 获取节点的第 k 个祖先
public int getKthAncestor(int node, int k) {
for (int j = 0; j < LOG; j++) {
if (((k >> j) & 1) != 0) { // 判断第 j 位是否为 1
node = ancestors[node][j]; // 更新当前节点为其第 j 级祖先
if (node == -1) { // 若当前节点为空,则返回 -1
return -1;
}
}
}
return node; // 返回第 k 个祖先节点
}
}
/**
* Your TreeAncestor object will be instantiated and called as such:
* TreeAncestor obj = new TreeAncestor(n, parent);
* int param_1 = obj.getKthAncestor(node,k);
*/
版权声明:本文为博主作者:阿林爱吃大米饭原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/qq_51775901/article/details/137428044