T1483.树节点的第 K 个祖先

LCA, binary lifting, https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/

给你一棵树，树上有 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 * 10^4
parent[0] == -1 表示编号为 0 的节点是根节点。
对于所有的 0 < i < n ，0 <= parent[i] < n 总成立
0 <= node < n
至多查询 5 * 10^4 次

这道题目是倍增法（Binary Lifting）的经典模板题。

为了在 $O (\log k)$ 的时间内找到第 $k$ 个祖先，我们需要在初始化时预处理出一个“跳跃表”。

解题思路

预处理 (Initialization):
- 我们创建一个二维数组 up[i][node]，表示节点 node 的第 $2^{i}$ 个祖先。
- up[0] 就是题目给出的 parent 数组（即第 $2^{0} = 1$ 个祖先）。
- 递推公式：up[i][node] = up[i-1][up[i-1][node]]。
  - 意思是：跳 $2^{i}$ 步等于先跳 $2^{i - 1}$ 步，再跳 $2^{i - 1}$ 步。
- 如果某个祖先是 -1，则更高级别的祖先也都是 -1。
查询 (Query):
- 将 $k$ 拆解为二进制。例如 $k = 13$ ，其二进制为 1101，即 $13 = 8 + 4 + 1$ 。
- 我们要找第 13 个祖先，就让节点先跳 8 步，再跳 4 步，最后跳 1 步。
- 利用位运算 (k >> i) & 1 来判断 $k$ 的二进制第 $i$ 位是否为 1。
Python 代码实现

python

from typing import List

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        # n 最大 5*10^4，2^16 = 65536，所以 16 层左右就够了
        # 我们取 16 或 17 
        self.LOG = 16
        
        # self.up[i][node] 表示节点 node 的第 2^i 个祖先
        # self.up[0] 是直接父节点
        self.up = [parent]
        
        for i in range(1, self.LOG):
            prev_up = self.up[i-1]
            # 计算当前这一层：跳 2^i 步
            # 逻辑：从 j 跳 2^(i-1) 步到 prev_up[j]，再从那里跳 2^(i-1) 步
            curr_up = [
                prev_up[prev_up[j]] if prev_up[j] != -1 else -1 
                for j in range(n)
            ]
            self.up.append(curr_up)

    def getKthAncestor(self, node: int, k: int) -> int:
        for i in range(self.LOG):
            # 检查 k 的二进制表示中，第 i 位是否为 1
            if (k >> i) & 1:
                node = self.up[i][node]
                # 如果已经跳出根节点了，提前结束
                if node == -1:
                    break
        return node

# 示例运行逻辑：
# obj = TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2])
# param_1 = obj.getKthAncestor(3, 1) # 返回 1

复杂度分析

时间复杂度:
- 初始化: $O (n \log n)$ 。我们需要填充一个 $16 \times n$ 的表格。
- 查询: $O (\log k)$ 。对于每次查询，我们只需要遍历二进制位（最多 16 次）。
空间复杂度: $O (n \log n)$ 。用于存储 up 数组。

为什么这个解法高效？

如果使用暴力法（一个一个向上找），最坏情况下（树是一条长链）查询时间是 $O (n)$ ，总时间复杂度会达到 $O (n \cdot queries) \approx 2.5 \times 10^{9}$ ，这在 Python 中是绝对无法通过的。倍增法将单次查询降到了 $O (\log n)$ ，使得总计算量降到了 $10^{6}$ 级别，非常轻松。

T1483.树节点的第 K 个祖先 ​

T1483.树节点的第 K 个祖先