What is the primary technique for fast kth ancestor queries in this problem?

Binary lifting with a DP table of 2^j-th ancestors enables each query to execute in O(log k) time.

Can getKthAncestor return -1?

Yes, if the node does not have a kth ancestor, the method should return -1 immediately.

What is the space complexity of precomputing ancestors?

Storing the DP table for all nodes and all powers of two ancestors requires O(n log n) space.

How does GhostInterview help with large numbers of queries?

It ensures all queries use precomputed states, avoiding linear traversal and time limit exceeded errors.

Is binary-tree traversal always necessary in this problem?

Traversal is needed initially to build ancestor relationships, but subsequent queries rely on precomputed jumps rather than repeated traversal.

#1483

Hard

auto_awesome二分·树·traversal

LeetCode 题解工作台

树节点的第 K 个祖先

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。实现 TreeAncestor 类： TreeAncestor…

二分查找动态规划树深度优先搜索广度优先搜索

题目描述

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

lightbulb

解题思路

方法一：动态规划 + 倍增

题目要我们寻找节点 $node$ 的第 $k$ 个祖先节点，如果暴力求解，需要从 $node$ 开始向上遍历 $k$ 次，时间复杂度为 $O(k)$ ，显然会超时。

我们可以使用动态规划，结合倍增的思想来处理。

我们定义 $p[i][j]$ 表示节点 $i$ 的第 $2^j$ 个祖先节点，即 $p[i][j]$ 表示节点 $i$ 向上走 $2^j$ 步的节点。那么我们可以得到状态转移方程：

p[i][j] = p[p[i][j-1]][j-1]

即：要想找到节点 $i$ 的第 $2^j$ 个祖先节点，我们可以先找到节点 $i$ 的第 $2^{j-1}$ 个祖先节点，然后再找到该节点的第 $2^{j-1}$ 个祖先节点即可。所以，我们要找到每个节点的距离为 $2^j$ 的祖先节点，直到达到树的最大高度。

之后对于每次查询，我们可以把 $k$ 拆成二进制的表示形式，然后根据二进制中 $1$ 的位置，累计向上查询，最终得到节点 $node$ 的第 $k$ 个祖先节点。

时间复杂度方面，初始化为 $O(n \times \log n)$ ，查询为 $O(\log n)$ 。空间复杂度 $O(n \times \log n)$ 。其中 $n$ 为树的节点数。

相似题目：

2836. 在传球游戏中最大化函数值

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class TreeAncestor:
    def __init__(self, n: int, parent: List[int]):
        self.p = [[-1] * 18 for _ in range(n)]
        for i, fa in enumerate(parent):
            self.p[i][0] = fa
        for j in range(1, 18):
            for i in range(n):
                if self.p[i][j - 1] == -1:
                    continue
                self.p[i][j] = self.p[self.p[i][j - 1]][j - 1]

    def getKthAncestor(self, node: int, k: int) -> int:
        for i in range(17, -1, -1):
            if k >> i & 1:
                node = self.p[node][i]
                if node == -1:
                    break
        return node


# Your TreeAncestor object will be instantiated and called as such:
# obj = TreeAncestor(n, parent)
# param_1 = obj.getKthAncestor(node,k)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate uses binary lifting or another logarithmic ancestor retrieval method.
question_mark
Listen for explanations on how state propagation in the tree avoids redundant traversal.
question_mark
Watch for awareness of edge cases when k exceeds the node's depth.

warning

常见陷阱

外企场景

error
Attempting to traverse up k steps linearly for each query, causing time limit exceeded errors.
error
Not initializing ancestor table correctly, leading to incorrect returns for nodes near the root.
error
Ignoring the binary representation approach, missing the opportunity for logarithmic query optimization.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the lowest common ancestor (LCA) for multiple pairs of nodes using similar binary lifting preprocessing.
arrow_right_alt
Determine the distance between any two nodes efficiently using ancestor jumps.
arrow_right_alt
Support dynamic tree modifications with online ancestor queries, requiring updated state propagation.

help

常见问题

外企场景

继续练习

#1261 在受污染的二叉树中查找元素 #1993 树上的操作 #1457 二叉树中的伪回文路径