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

这篇具有很好参考价值的文章主要介绍了lc 1483 树节点的第 K 个祖先（树上倍增、动态规划）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

lc 1483 树节点的第 K 个祖先文章来源地址https://www.toymoban.com/news/detail-860974.html

我们定义：节点的第 i 级父节点为第 $2^i$ 个父节点
规律1：节点的第 n 个父节点 = 节点的第 $n_i$ 个父节点的第 $n_j$ 个父节点，其中 $n_i+n_j=n$ 。
- （倍增）以二进制为基础，节点 i 的第 $2^j$ 个父节点 = 节点 i 的第 $2^{j-1}$ 个父节点的第 $2^{j-1}$ 个父节点，即 $an ces t ors [i] [j] = an ces t ors [an ces t ors [i] [j - 1]] [j - 1]$ （动态规划）
- 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);
 */