树节点的第 K 个祖先【LC1483】

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

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

实现 TreeAncestor 类：

• TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
• getKthAncestor``(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

新知识++

• 思路

  • 暴力：从每个node出发，往上跳$k$次，时间复杂度为$\mathcal{O}(mk)$，会超时

  • 优化：每次跳跃时不止跳一个节点->使用倍增算法，预处理每个节点的$2^i$个祖先节点，某个节点的第$2^{i+1}$个祖先节点为其第$2^i$个祖先节点的第$2^i$个祖先节点，如果其$2^i$个祖先节点不存在，那么后续的祖先节点也不存在。递推公式如下
    $$dp[x][i+1]=dp[dp[x][i]][i]$$

  • 每次查询的$k$可以由若干2的幂组成，因此可以快速到达第$k$个祖先节点。

• 实现

  class TreeAncestor {private int[] depth;private int[][] pa;public TreeAncestor(int[][] edges) {int n = edges.length + 1;int m = 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度List<Integer> g[] = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for (var e : edges) { // 节点编号从 0 开始int x = e[0], y = e[1];g[x].add(y);g[y].add(x);}depth = new int[n];pa = new int[n][m];dfs(g, 0, -1);for (int i = 0; i < m - 1; i++) {for (int x = 0; x < n; x++) {int p = pa[x][i];pa[x][i + 1] = p < 0 ? -1 : pa[p][i];}}}private void dfs(List<Integer>[] g, int x, int fa) {pa[x][0] = fa;for (int y : g[x]) {if (y != fa) {depth[y] = depth[x] + 1;dfs(g, y, x);}}}public int getKthAncestor(int node, int k) {for (; k > 0; k &= k - 1)node = pa[node][Integer.numberOfTrailingZeros(k)];return node;}public int getLCA(int x, int y) {if (depth[x] > depth[y]) {int tmp = y;y = x;x = tmp;}// 使 y 和 x 在同一深度y = getKthAncestor(y, depth[y] - depth[x]);if (y == x)return x;for (int i = pa[x].length - 1; i >= 0; i--) {int px = pa[x][i], py = pa[y][i];if (px != py) {x = px;y = py;}}return pa[x][0];}
  }作者：灵茶山艾府
  链接：https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/solutions/2305895/mo-ban-jiang-jie-shu-shang-bei-zeng-suan-v3rw/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  

  • 复杂度
    • 时间复杂度：预处理$\mathcal{O}(n\log n)$，每个询问$\mathcal{O}(\log n)$
    • 空间复杂度：预处理$\mathcal{O}(n\log n)$