lc 1483 树节点的第 K 个祖先（树上倍增、动态规划）

lc 1483 树节点的第 K 个祖先

• 我们定义：节点的第 i 级父节点为第 个父节点
• 规律1：节点的第 n 个父节点 = 节点的第 个父节点的第 个父节点，其中。
  • （倍增）以二进制为基础，节点 i 的 第 个父节点 = 节点 i 的第 个父节点的第 个父节点，即 （动态规划）
  • if (((k >> j) & 1) != 0) // 判断第 j 位是否为 1
    • 若是1
      • 有父节点 -> 往第 j 级父节点向上
      • 没有父节点 -> 原题无解
    • 若不是1，continued;

// 题解参考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);
 */