LeetCode 1483: Kth Ancestor of a Tree Node
Problem Description
Explanation:
To efficiently find the kth ancestor of a given node in a tree, we can precompute the ancestors of each node using dynamic programming. We can store the parent of each node at various powers of 2 in a 2D array, where dp[i][j] represents the 2^j-th ancestor of node i.
- Initialization: Initialize the dp array to store the direct parent of each node.
- Compute Ancestors: For each power of 2, iterate through all nodes and compute the ancestor at that power.
- Query for Kth Ancestor: To find the kth ancestor of a node, we use binary decomposition of k to jump to the appropriate ancestor in logarithmic time.
Time Complexity:
- Preprocessing: O(n log n)
- Query: O(log k)
Space Complexity:
- O(n log n)
:
Solutions
class TreeAncestor {
int[][] dp;
public TreeAncestor(int n, int[] parent) {
int maxPower = (int)(Math.log(n) / Math.log(2)) + 1;
this.dp = new int[n][maxPower];
for (int i = 0; i < n; i++) {
dp[i][0] = parent[i];
}
for (int j = 1; j < maxPower; j++) {
for (int i = 0; i < n; i++) {
if (dp[i][j-1] != -1) {
dp[i][j] = dp[dp[i][j-1]][j-1];
} else {
dp[i][j] = -1;
}
}
}
}
public int getKthAncestor(int node, int k) {
int maxPower = dp[0].length;
for (int i = 0; i < maxPower; i++) {
if ((k & (1 << i)) > 0) {
node = dp[node][i];
if (node == -1) return -1;
}
}
return node;
}
}Loading editor...