LC.P1483[树节点的第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
class TreeAncestor {

    int[][] p;
    int m;

    public TreeAncestor(int n, int[] parent) {
        m = 32 - Integer.numberOfLeadingZeros(n); // n的二进制长度
        p = new int[n][m];
        for (int i = 0; i < n; ++i) p[i][0] = parent[i];
        for (int i = 0; i < m - 1; ++i) {
            for (int x = 0; x < n; ++x) {
                int cur = p[x][i];
                p[x][i + 1] = cur < 0 ? -1 : p[cur][i];
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        for (int i = 0; i < m; ++i) {
            // k的二进制从低到高第i位是1
            if (((k >> i) & 1) > 0) {
                node = p[node][i];
                if (node < 0) break;
            }
        }
        return node;
    }
}

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor obj = new TreeAncestor(n, parent);
 * int param_1 = obj.getKthAncestor(node,k);
 */
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(nlogn)$