这道题是 “树节点的第 K 个祖先”，经典的 树上倍增（Binary Lifting） 问题。核心思想是预处理每个节点的 2^j 级祖先，然后利用二进制分解在 O(log N) 时间内查询。

题目理解

• 给定一棵树（节点编号 0…n-1，根节点为 0）
• parent[i] 表示节点 i 的父节点（根节点的父节点为 -1）
• 需要实现 getKthAncestor(node, k)：返回 node 的第 k 个祖先，不存在则返回 -1

关键约束：查询次数可能很多（最多 5×10⁴），需要 O(log N) 或 O(1) 的查询。

核心解法：树上倍增

预处理

定义 up[node][j] = 节点 node 向上走 2^j 步到达的祖先节点

• up[node][0] = parent[node]（2⁰ = 1 步）
• up[node][j] = up[ up[node][j-1] ][j-1]（先走 2^(j-1) 步，再走 2^(j-1) 步）

查询

将 k 分解为二进制，从低位到高位依次向上跳：

例如 k = 13 = 1101₂ = 8 + 4 + 1
先跳 1 步，再跳 4 步，再跳 8 步

完整代码

class TreeAncestor {
    private int[][] up;      // up[node][j] = node 的 2^j 级祖先
    private int n;
    private int maxLog;
    
    public TreeAncestor(int n, int[] parent) {
        this.n = n;
        // 计算最大需要的二进制位数
        this.maxLog = (int)(Math.log(n) / Math.log(2)) + 1;
        
        // 初始化 up 数组
        up = new int[n][maxLog];
        for (int i = 0; i < n; i++) {
            Arrays.fill(up[i], -1);  // -1 表示不存在
        }
        
        // 2^0 级祖先 = 父节点
        for (int i = 0; i < n; i++) {
            up[i][0] = parent[i];
        }
        
        // 动态规划填充 up 数组
        for (int j = 1; j < maxLog; j++) {
            for (int i = 0; i < n; i++) {
                if (up[i][j - 1] != -1) {
                    up[i][j] = up[ up[i][j - 1] ][j - 1];
                }
            }
        }
    }
    
    public int getKthAncestor(int node, int k) {
        // 如果 k 太大，直接返回 -1
        if (k > (1 << maxLog)) {
            return -1;
        }
        
        int current = node;
        // 二进制分解
        for (int j = 0; j < maxLog; j++) {
            if (((k >> j) & 1) == 1) {
                current = up[current][j];
                if (current == -1) {
                    return -1;
                }
            }
        }
        return current;
    }
}

优化版本：使用二进制长度计算

class TreeAncestor {
    private int[][] up;
    private int n;
    private int maxLog;
    
    public TreeAncestor(int n, int[] parent) {
        this.n = n;
        // 计算最大需要的层数：log2(n) + 1
        this.maxLog = 32 - Integer.numberOfLeadingZeros(n);  // 等价于 floor(log2(n)) + 1
        // 或者：this.maxLog = Integer.toBinaryString(n).length();
        
        up = new int[n][maxLog];
        
        // 初始化：2^0 级祖先
        for (int i = 0; i < n; i++) {
            up[i][0] = parent[i];
        }
        
        // 倍增预处理
        for (int j = 1; j < maxLog; j++) {
            for (int i = 0; i < n; i++) {
                int mid = up[i][j - 1];
                up[i][j] = (mid == -1) ? -1 : up[mid][j - 1];
            }
        }
    }
    
    public int getKthAncestor(int node, int k) {
        int current = node;
        // 遍历每一位
        for (int j = 0; j < maxLog && current != -1; j++) {
            if ((k & (1 << j)) != 0) {
                current = up[current][j];
            }
        }
        return current;
    }
}

空间优化：使用 List 存储

如果 n 很大（如 5×10⁴）但 maxLog 较小（约 16），可以使用 List 数组：

class TreeAncestor {
    private List<Integer>[] up;
    
    public TreeAncestor(int n, int[] parent) {
        int maxLog = 32 - Integer.numberOfLeadingZeros(n);
        up = new List[n];
        
        for (int i = 0; i < n; i++) {
            up[i] = new ArrayList<>();
            up[i].add(parent[i]);  // 2^0 祖先
        }
        
        for (int j = 1; j < maxLog; j++) {
            for (int i = 0; i < n; i++) {
                int prev = up[i].get(j - 1);
                if (prev != -1) {
                    up[i].add(up[prev].get(j - 1));
                } else {
                    up[i].add(-1);
                }
            }
        }
    }
    
    public int getKthAncestor(int node, int k) {
        int current = node;
        for (int j = 0; j < up[0].size() && current != -1; j++) {
            if ((k & (1 << j)) != 0) {
                current = up[current].get(j);
            }
        }
        return current;
    }
}

时间复杂度分析

示例演示

输入: n = 7, parent = [-1,0,0,1,1,2,2]
树结构:
        0
       / \
      1   2
     / \ / \
    3  4 5 6

查询: getKthAncestor(6, 2)
- 6 的 2^0=1 级祖先: 2
- 2 的 2^0=1 级祖先: 0
- 结果: 0

预处理 up[6]:
- up[6][0] = 2
- up[6][1] = up[2][0] = 0
- up[6][2] = up[0][1] = -1

进阶优化：使用 DFS 时间戳 + 二分

对于静态树，也可以用 欧拉序 + 深度数组 + 二分查找，但实现更复杂，且查询 O(log n) 但常数更大。

常见错误

1. maxLog 计算错误：确保 2^maxLog > n，否则可能跳过头
2. 数组越界：访问 up[current][j] 前检查 current != -1
3. 未处理 -1 情况：祖先不存在时应立即返回 -1
4. 使用 1-indexed 节点：题目是 0-indexed，注意转换

总结

树上倍增是解决静态树祖先查询的标准方法：

• 预处理：O(n log n) 计算每个节点的 2^j 级祖先
• 查询：O(log n) 二进制分解向上跳
• 空间：O(n log n) 存储倍增表

这是 LeetCode 上 LCA（最近公共祖先） 问题的基础，掌握后可以扩展到更复杂的树上查询问题。