树节点的第 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次，时间复杂度为O(mk)，会超时 - 优化：每次跳跃时不止跳一个节点->使用倍增算法，预处理每个节点的2i个祖先节点，某个节点的第2i+1个祖先节点为其第2i个祖先节点的第2i个祖先节点，如果其2i祖先节点不存在，那么后续的祖先节点也不存在。递推公式如下
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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：预处理O(nlogn)，每个询问O(logn)
- 空间复杂度：预处理O(nlogn)
