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

2022-11-01 HGNULB 约 6 分钟

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

分类

LeetCode CodeTop 困难 未解决 2-5 字节 微软

标签

动态规划 深度优先搜索 树 广度优先搜索 二分查找 设计 位运算

题目描述

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

题意分析

给定一棵树的父节点数组，需要多次查询从 node 连续向上走 k 条边后到达的祖先；如果途中已经越过根节点，返回 -1。

每次逐层找父节点需要走 k 次。树本身不会变化，可以先记录每个节点向上走 1、2、4、8…… 步的结果，再把查询步数拆成这些二的幂。

解法：倍增预处理祖先表

核心思路

[!blue]

定义 up[v][j] 为节点 v 向上走 2^j 步后到达的节点，不存在时为 -1。第 0 列走一步，直接使用 parent[v]；更长的一次跳跃可以拆成两段相同长度的跳跃。

计算第 j 列时，先令 p = up[v][j-1]，走完前半段。如果 p == -1，说明前半段都无法完成，更长祖先也不存在；否则再从 p 走 2^(j-1) 步，得到 up[v][j] = up[p][j-1]。

预处理必须先算完所有节点的第 j-1 列，再计算第 j 列，因为第二段可能访问任意编号的祖先节点。父节点的编号不保证更小，不能按节点逐行填完整张表。

查询时，从低位到高位检查 k 的二进制位。第 j 位为 1，就把当前 node 更新为 up[node][j]；为 0 则不动。每次跳跃都从上一次到达的节点继续，处理完所有置位后，总步数恰好等于 k。若中途变成 -1，更远处也不存在祖先，立即结束即可。

题目保证 k <= n。代码令 maxLog 为满足 2^maxLog > n 的最小正整数，因此 0..maxLog-1 列覆盖所有可能用到的二进制位。

解题步骤

1. 根据 n 算出表的列数，将每个节点的第 0 列设为直接父节点。
2. 从小到大枚举列 j，对全部节点合并两段 2^(j-1) 步跳跃；不存在的祖先统一记录为 -1。
3. 查询时检查 k 的各二进制位，置位就从当前节点按对应列跳跃。
4. 所有位处理完后返回当前节点；若中途已到达 -1，返回 -1。

代码实现

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) {
                // k 的第 j 个二进制位为 1，就从当前节点向上跳 2^j 步。
                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 {
            // k 的第 j 个二进制位为 1，就从当前节点向上跳 2^j 步。
            node = t.up[node][j]
        }
    }
    return node
}

复杂度分析

• 时间复杂度：预处理为 $O(n\log(n+1))$，每个表格位置只计算一次；单次查询为 $O(\log(n+1))$，最多检查全部列。
• 空间复杂度：$O(n\log(n+1))$，用于保存每个节点的倍增祖先表。

关键点总结

[!green]

• 表的列号是步数的指数，up[v][j] 跳 2^j 步，而不是跳 j 步。
• 长跳跃依赖两个同长度短跳跃，按列填表才能保证依赖已经准备好。
• 查询中的当前节点持续改变，所选步长之和恰好是目标 k。
• -1 表示祖先不存在，必须先判断，不能把它继续当作数组下标。

易错点总结

[!yellow]

• 用默认值 0 表示不存在，会把缺失祖先误认成根节点；根的父节点及更远祖先应为 -1。
• 没检查中间祖先 p 就访问 up[p]，会在到达根上方时越界。
• 每次都从最初的 node 跳跃，而不更新当前节点，得到的步数不会累加。
• 按节点逐行预处理，可能读取编号更大的父节点尚未计算的列。
• 忽略最高一位的覆盖要求，会漏掉 k 中最大的跳跃距离；表宽应满足 2^maxLog > n。

相似题目

题目	难度	关联与区别
236. 二叉树的最近公共祖先	中等	最近公共祖先查询可用倍增先把深度对齐，再同时向上跳；本题提供固定步数祖先查询。
50. Pow(x, n)	中等	同样按二进制拆分重复次数，本题把祖先关系预合成为2的幂步长。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/44583981

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！