LeetCode 1483. 树节点的第 K 个祖先

2022-11-01 HGNULB 约 11 分钟

文章信息 7 个分类 8 个标签

分类

题目描述

✅ 1483. 树节点的第 K 个祖先

题意分析

给定一棵 $n$ 个节点的有根树，节点编号 $0$ 到 $n-1$，根是 $0$，用 parent 数组给出每个节点的父节点（根的父节点是 $-1$）。要设计一个类，支持大量 getKthAncestor(node, k) 查询：返回 node 向上第 $k$ 层的祖先，不存在（跳出根之外）返回 $-1$。

这是一道设计题，所以必须分开算两笔账：构造时的一次性预处理开销和单次查询的开销。题目明确说查询次数可达 $5 \times 10^4$，节点数也到 $5 \times 10^4$，这是在告诉你：单次查询哪怕只是 $O(n)$，最坏也要 $2.5 \times 10^9$ 步，必须把单次查询压到对数级，代价是允许在构造时多花时间和空间。

parent 数组直接给出的是「往上一步」的映射，也就是每个节点的第 $1$ 级祖先。查询要的是「往上 $k$ 步」。$k$ 的范围与 $n$ 同阶，所以本质上是在一个函数式图（每个点出度恰为 1）上做 $k$ 次迭代，问的是 $k$ 次复合后的像。

边界有三处：node 本身是根时，任何 $k \ge 1$ 都返回 $-1$；$k$ 大于 node 的深度时同样返回 $-1$，中途一旦跳到 $-1$ 就必须停住而不能继续用 $-1$ 去索引数组；$k$ 可能取 $1$，此时答案就是 parent[node]。

解法：倍增预处理祖先表

核心思路

最朴素的做法是每次查询就顺着 parent 逐级往上走 $k$ 步。单次 $O(k)$，最坏 $O(n)$，乘上 $5 \times 10^4$ 次查询就是 $2.5 \times 10^9$，超时。另一个极端是预处理出每个节点的全部祖先列表（等价于根到该节点的路径），查询 $O(1)$，但一条链形树的路径总长是 $O(n^2) = 2.5 \times 10^9$ 个整数，空间爆炸。

两个极端都不可取，说明要在预处理量与查询量之间找折中。突破口是二进制拆分：任何 $k$ 都可以唯一写成若干个不同 $2$ 的幂之和（就是它的二进制表示），$k \le n$ 时最多用到 $\lceil \log_2 n \rceil$ 个幂。如果我们能 $O(1)$ 地完成「向上跳 $2^j$ 步」，那么一次查询只需按 $k$ 的二进制位做至多 $\log n$ 次大跳。

于是定义倍增表，这是本解法的核心状态定义：up[i][j] 表示节点 $i$ 向上跳 $2^j$ 步到达的祖先，若跳出根则为 $-1$。$j = 0$ 一层就是 parent 本身。

递推关系来自幂的可加性：跳 $2^j$ 步等于先跳 $2^{j-1}$ 步、再从落点跳 $2^{j-1}$ 步。写成状态转移就是 up[i][j] = up[ up[i][j-1] ][j-1]，其中若中间落点已是 $-1$，则整体也是 $-1$（跳出根之后再怎么跳都出不来）。这个「先半程再半程」的结构和快速幂中 $x^{2m} = (x^m)^2$ 是同一个思想，只不过这里复合的是「取父节点」这个函数而不是乘法。

表的列数取 $\lceil \log_2 n \rceil + 1$ 就够：任何合法的 $k$ 都不超过 $n$（超过必然跳出根返回 $-1$，而这条路径上总会先跳到 $-1$ 并停住），所以 $k$ 的二进制位不会超出这个范围。

查询时的不变量是：处理完第 $j$ 位后，node 是原始节点向上 $k \bmod 2^{j+1}$ 步的祖先，或已变成 $-1$。逐位从低到高检查 $k$，该位为 $1$ 就把 node 换成它的 $2^j$ 级祖先，全部处理完刚好累计跳了 $k$ 步。

解题步骤

先算出需要多少列 maxLog：从 $1$ 开始把 1 << log 与 $n$ 比较，直到 $2^{log} > n$。这样保证 $2^{maxLog - 1} \le n < 2^{maxLog}$，即任何 $k \le n$ 的二进制位都落在 $[0, maxLog)$ 内，查询循环不会漏位。多开一列只浪费 $O(n)$ 空间，少开一列会直接算错。

用 parent 填充第 $0$ 列：up[i][0] = parent[i]。这是递推的基，语义上「跳 $2^0 = 1$ 步」就是找父节点，根的这一项天然是 $-1$，把「越界」这个信息一并编码进了表里。

外层循环 $j$ 从 $1$ 到 maxLog - 1，内层循环 $i$ 遍历所有节点，做 up[i][j] = up[up[i][j-1]][j-1]。外层必须是 $j$、内层才是 $i$：计算第 $j$ 列时要用到任意节点的第 $j-1$ 列，如果按节点逐个填完整行，up[p][j-1] 可能还没算出来。这个循环顺序是倍增表最容易写反的地方。

递推时先判 p == -1 再索引。中间落点是 $-1$ 说明跳 $2^{j-1}$ 步已经出了根，那么跳 $2^j$ 步更出不来，直接置 $-1$；不判就会拿 $-1$ 当下标，数组越界。

查询时按位遍历 $j$，(k >> j) & 1 为 $1$ 才跳。这里对 $k$ 做的正是二进制分解，每一位对应一次「是否使用这个大小的跳跃」。

循环条件里带上 node != -1 提前退出。一旦跳出根就没有必要也没有可能继续跳，且继续跳会以 $-1$ 索引数组；提前退出后返回的 $-1$ 正是题目要求的结果。

返回 node，此时它要么是正确的第 $k$ 级祖先，要么是 $-1$。

以 n = 7、parent = [-1, 0, 0, 1, 1, 2, 2]（一棵满二叉树，节点 3 的祖先链是 $3 \to 1 \to 0$）走一遍：

算列数：$2^1 = 2 \le 7$、$2^2 = 4 \le 7$、$2^3 = 8 > 7$，所以 maxLog = 3，表是 $7 \times 3$。
第 $0$ 列直接抄 parent：up[*][0] = [-1, 0, 0, 1, 1, 2, 2]。
第 $1$ 列（跳 2 步）：up[0][1] 的中间落点是 $-1$，置 $-1$；up[1][1] = up[0][0] = -1；up[2][1] = up[0][0] = -1；up[3][1] = up[1][0] = 0；up[4][1] = up[1][0] = 0；up[5][1] = up[2][0] = 0；up[6][1] = up[2][0] = 0。
第 $2$ 列（跳 4 步）：所有节点的中间落点要么是 $-1$、要么是 $0$，而 up[0][1] = -1，所以整列全是 $-1$。
查询 getKthAncestor(3, 1)：$k = 1$ 的二进制是 001。$j = 0$ 位为 $1$，node = up[3][0] = 1；$j = 1$ 位为 $0$ 跳过；$j = 2$ 位为 $0$ 跳过。返回 $1$。
查询 getKthAncestor(5, 2)：$k = 2$ 的二进制是 010。$j = 0$ 位为 $0$；$j = 1$ 位为 $1$，node = up[5][1] = 0；$j = 2$ 位为 $0$。返回 $0$。
查询 getKthAncestor(6, 3)：$k = 3$ 的二进制是 011。$j = 0$ 位为 $1$，node = up[6][0] = 2；$j = 1$ 位为 $1$，node = up[2][1] = -1；此时循环条件 node != -1 不再成立，直接退出。返回 $-1$。节点 6 的深度是 2，向上 3 步确实越过了根。

注意最后一次查询里，$3 = 1 + 2$ 被拆成先跳 1 步再跳 2 步，两次大跳合起来正好 3 步——这就是二进制分解在起作用。

代码实现

class TreeAncestor {
    private final int[][] up;
    private final int maxLog;

    public TreeAncestor(int n, int[] parent) {
        int log = 1;
        while ((1 << log) <= n) {
            log++;
        }
        maxLog = log;
        up = new int[n][maxLog];

        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 p = up[i][j - 1];
                if (p == -1) {
                    up[i][j] = -1;
                } else {
                    up[i][j] = up[p][j - 1];
                }
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        for (int j = 0; j < maxLog && node != -1; j++) {
            if (((k >> j) & 1) == 1) {
                node = up[node][j];
            }
        }
        return node;
    }
}

type TreeAncestor struct {
    up     [][]int
    maxLog int
}

func Constructor(n int, parent []int) TreeAncestor {
    log := 1
    for (1 << log) <= n {
        log++
    }

    up := make([][]int, n)
    for i := 0; i < n; i++ {
        up[i] = make([]int, log)
        up[i][0] = parent[i]
    }

    for j := 1; j < log; j++ {
        for i := 0; i < n; i++ {
            p := up[i][j-1]
            if p == -1 {
                up[i][j] = -1
            } else {
                up[i][j] = up[p][j-1]
            }
        }
    }

    return TreeAncestor{up: up, maxLog: log}
}

func (t *TreeAncestor) GetKthAncestor(node int, k int) int {
    for j := 0; j < t.maxLog && node != -1; j++ {
        if (k>>j)&1 == 1 {
            node = t.up[node][j]
        }
    }
    return node
}

复杂度分析

时间复杂度：构造 $O(n \log n)$，单次查询 $O(\log n)$。构造时要填满 $n \times \lceil \log_2 n \rceil$ 个表项，每项是一次数组读取加一次判空，都是常数；查询时最多遍历 $\log n$ 个二进制位，每位最多一次表查询。$n = 5 \times 10^4$ 时构造约 $8 \times 10^5$ 步，$5 \times 10^4$ 次查询共约 $8 \times 10^5$ 步，都很宽裕。

空间复杂度：$O(n \log n)$。倍增表是二维的，行数是节点数、列数是 $\lceil \log_2 n \rceil + 1$，本题约 $5 \times 10^4 \times 17$ 个整数，不到 $4$ MB。这是拿空间换查询时间的典型定价：比「存全部祖先路径」的 $O(n^2)$ 小得多，比只存 parent 的 $O(n)$ 大 $\log n$ 倍。

关键点总结

设计题要先把「预处理」和「查询」两笔开销分开定价，再根据调用次数决定往哪边倾斜。查询远多于构造时，就该把成本前移。

二进制拆分是把线性次操作压成对数次的通用手法：只要操作可结合、可预先把 $2^j$ 次复合的结果算出来，任意次数都能用 $\log$ 个大步拼出来。快速幂、稀疏表、树上倍增都是同一个模子。

倍增表的递推 up[i][j] = up[up[i][j-1]][j-1] 必须按 $j$ 从小到大分层填，同层内节点顺序任意。搞错循环嵌套顺序会读到未初始化的表项，且不会报错，只会静默出错。

用 $-1$ 作为「越界」的哨兵值并让它在递推中自我传播（$-1$ 的任何级祖先仍是 $-1$），比额外维护深度数组更省事；但每次索引前必须显式判空。

面试视角：面试官会先问「为什么不逐级跳」，再问「为什么不预存全部祖先」，你要用两组数字把两端都堵死，然后自然引出倍增。接着大概率追问「这个表还能做什么」——答最近公共祖先（LCA）：先把深的那个节点倍增提到同一深度，再两点同步倍增上跳直到父节点相同。能主动提到 LCA 通常直接决定这轮的评价。

若树是静态且允许 $O(n)$ 预处理，还有欧拉序 + 稀疏表把 LCA 做到 $O(1)$ 查询的路子；倍增胜在实现短、易改写，是白板首选。

易错点总结

递推时把两层循环写反（外层节点、内层 $j$）：n = 7, parent = [-1,0,0,1,1,2,2] 时计算 up[3][1] 需要 up[1][0]，若按节点顺序先算完节点 3 的整行再算节点 1，在链形树上会读到尚未填好的 $0$ 值，getKthAncestor(3, 2) 返回 $0$ 之外的错误节点。

递推时不判中间落点为 $-1$：up[0][0] = -1，直接写 up[0][1] = up[-1][0] 在 Java 抛 ArrayIndexOutOfBoundsException，Go 直接 panic。

查询循环缺少 node != -1 的守卫：getKthAncestor(6, 3) 在跳完第二位后 node 变成 $-1$，若继续用 $-1$ 索引 up 会越界崩溃。

maxLog 算成 $\lfloor \log_2 n \rfloor$ 少了一列：n = 4、k = 4 时最高位 $j = 2$ 未被遍历，本该跳出根返回 $-1$ 的查询会返回一个真实存在的祖先。

按位判断写成 k & (1 << j) 后与 $1$ 比较：k = 4、j = 2 时 k & 4 等于 $4$ 不等于 $1$，条件恒假，所有高位跳跃被跳过，getKthAncestor(node, 4) 会原样返回 node。

第 $0$ 列忘记初始化，直接从 $j = 1$ 开始递推：Java 中 int[][] 默认全 $0$，getKthAncestor(3, 1) 会返回 $0$（恰好是根编号）而不是 $1$，错误极其隐蔽。

把根的父节点存成 $0$ 而不是 $-1$：getKthAncestor(0, 1) 会返回 $0$，即根成了自己的父亲，且越界信息永远传播不出去，所有超深查询都返回 $0$。

查询时从高位向低位遍历却仍用 k >> j & 1：本身没错，但若顺手把「剩余步数」也做减法而忘记同步，k = 3 会只跳 2 步，getKthAncestor(6, 3) 返回 $0$ 而非 $-1$。

构造时把表开成 new int[maxLog][n] 但访问用 up[i][j]：$n$ 与 maxLog 不等时（本题 $n = 7$、maxLog = 3）访问 up[3][1] 直接越界。

误以为 $k$ 可能大于 $n$ 就需要提前取模：$k$ 大于深度时应当返回 $-1$ 而不是绕回，取模会让 getKthAncestor(3, 8) 返回节点 $1$，正确答案是 $-1$。

相似题目

题目	难度	考察点
236. 二叉树的最近公共祖先	中等	单次查询用递归回溯即可，多次查询才需要本题的倍增表把两点提到同深度
1650. 二叉树的最近公共祖先 III	中等	节点自带父指针，可用双指针换轨法在 $O(1)$ 空间内求 LCA，无需预处理
1123. 最深叶节点的最近公共祖先	中等	需自底向上同时返回深度与候选祖先，考的是后序信息聚合而非跳跃
50. Pow(x, n)	中等	同为二进制拆分做 $\log$ 次大步，复合的是乘法而非取父节点
239. 滑动窗口最大值	困难	稀疏表是倍增思想在区间极值上的版本，本题用单调队列做在线更优
287. 寻找重复数	中等	同为函数式图上的迭代，但用快慢指针找环入口而非预处理跳表
1206. 设计跳表	困难	同为多层指针加速跳跃，层高随机而非固定为 $2$ 的幂，且支持动态插删
剑指 Offer 22. 链表中倒数第k个节点	简单	单链上的第 $k$ 级前驱，单次查询用双指针 $O(n)$ 即可，无需建表