Ricky.L的随笔
0%

LeetCode.1483.树节点的第 K 个祖（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.1483.树节点的第 K 个祖（困难）

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

请你设计并实现 getKthAncestor(int node, int k) 函数，函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

题解

预处理

  • go[i][x]表示结点x的第 2的i次幂 个祖先结点，即x往上跳 2的i次幂 后达到的结点。
  • x跳2的i次幂步可以分解为先跳了2的i-1次幂步，再跳2的i-1次幂步。
  • 从x跳2的i-1次幂步后的到达的结点为go[i-1][x]，令其为y。
  • 再跳2的i-1次幂步后到达的结点为go[i-1][y]。
  • 则go[i][x] = go[i-1][y] = go[i-1][go[i-1][x]]。

优化

  • 把i放在二维数组的第一维，x放在二维数组的第二维。
  • 因为i的取值范围很小，n可能很大。
  • 将小维度的循环放在外层，可以提高缓存的命中率，进而提高程序运行速度。

i的取值范围是多少？

二叉树有n个结点，树高最多n层，退化为一个长度为n链表，最坏情况下就是求叶结点的第n-1个祖先。

用1 + $log_2{(n-1)}$（向下取整）个二进制位足以表示n-1。

例如8的二进制是1000，16的二进制位10000，8是2的3次幂，16是2的4次幂。

大于等于8小于16的数用4位二进制就可以表示：1000、1001、1010、1011、1100、1101、1110、1111。

所以n-1可以用多少位二进制表示，求$log_2{(n-1)}$后向下取整再加1即可

怎么求第k个祖先？

把k拆解为2的幂的和，即检查k的二进制的每一位是否是1，第i位是1就往上跳2的i次幂步，这样最多检查（跳）1 + $log_2{(n-1)}$次，因为有效的k最大也就是n-1，n-1用1 + $log_2{(n-1)}$个二进制位可以表示，所以可在O($log_2{n}$)时间内找到第k个祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import kotlin.math.log2

/**
 * 倍增法
 */
class TreeAncestor(n: Int, parent: IntArray) {
    /**
     * 二叉树有n个结点，树高最多n层，退化为一个长度为n链表，最坏情况下就是求叶结点的第n-1个祖先
     *
     * 用1 + log_2{n}（向下取整）个二进制位足以表示n
     * 例如8的二进制是1000，16的二进制位10000，8是2的3次幂，16是2的4次幂
     * 大于等于8小于16的数用4位二进制就可以表示：1000、1001、1010、1011、1100、1101、1110、1111
     * 所以n可以用多少位二进制表示，对n向下取整再加1即可求得
     */
    private val bits = log2((n - 1).toDouble()).toInt() + 1

    /**
     * go[i][x]表示结点x的第 2的i次幂 个祖先结点，即x往上跳 2的i次幂 后达到的结点
     *
     * x跳 2的i次幂 步可以分解为先跳了 2的i-1次幂 步，再跳 2的i-1次幂 步
     * 从x跳 2的i-1次幂 步后的到达的结点为go[i-1][x]，令其为y
     * 再跳 2的i-1次幂 步后到达的结点为go[i-1][y]
     * 则go[i][x] = go[i-1][go[i-1][x]]
     *
     * 为什么要把i放在二维数组的第一维，x放在二维数组的第二维？
     * 因为i的取值范围很小，n可能很大
     * 将小维度的循环放在外层，可以提高缓存的命中率，进而提高程序运行速度
     * 因为内存从外存读取数据是按块读取的，CPU从内存读取数据到CPU缓存也是按块的
     */
    private val go = Array(bits) { IntArray(n) { -1 } }

    // 预处理时间复杂度O(n * log n)
    init {
        // go[i][x] = go[i-1][go[i-1][x]]
        // 求go[i][x]是依赖于前一步的，需要初始化最一开始的情景
        // i最小取0，go[0][x]为x的第1个（第2的0次幂个）祖先结点，即x的父结点

        // 每个结点的第 2的0次幂 个祖先，即第1个祖先，就是它们的直接父结点
        for (i in 0 until n) {
            go[0][i] = parent[i]
        }

        // 依次求出每个结点x往上跳 2的1次幂、2的2次幂...2的bits-1次幂 步后到达的结点
        for (i in 1 until bits) {
            for (x in 0 until n) {
                if (go[i - 1][x] != -1) {
                    // x往上跳 2的i次幂 步，可以看作是先跳了 2的i-1次幂 步，再跳 2的i-1次幂 步
                    // 从结点x往上先跳 2的i-1次幂 步后到达的结点是go[i - 1][x]，设其为y，y在前一轮循环已经求过了
                    // 从结点y往上再跳 2的i-1次幂 步后达到的结点，在上一轮循环也求过了
                    // 所以这个递推关系就可以顺利进行
                    go[i][x] = go[i - 1][go[i - 1][x]]
                } else {
                    // 之前已经往上跳到根结点了，后面也没必要再跳了
                    go[i][x] = -1
                }
            }
        }
    }

    /**
     * 把k拆分为2的幂的和
     *
     * 查询时间复杂度O(log n)
     */
    fun getKthAncestor(node: Int, k: Int): Int {
        var ancestor = node
        for (i in bits - 1 downTo 0) {
            // k的二进制在第i位为0，不往上跳
            val mask = 1 shl i
            if (k and mask == 0) continue
            // k的二进制在第i位为1，可以往上跳 2的i次幂 步
            ancestor = go[i][ancestor]
            // 不存在node的第k个祖先
            if (ancestor == -1) break
        }
        return ancestor
    }
}