1483.树节点的第K个祖先
链接：1483.树节点的第K个祖先
难度：Hard
标签：树、深度优先搜索、广度优先搜索、设计、二分查找、动态规划
简介：给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
题解 1 - cpp
- 编辑时间：2023-06-12
- 执行用时：520ms
- 内存消耗：132.2MB
- 编程语言：cpp
- 解法介绍：倍增法。
class TreeAncestor {
public:
vector<vector<int>> list;
TreeAncestor(int n, vector<int>& parent): list(vector<vector<int>>(n)) {
for (int i = 1; i < parent.size(); i++) {
list[i].push_back(parent[i]);
for (int j = 1, res = 1; res != -1; j++) {
res = getKthAncestor(i, pow(2, j));
if (res != -1) list[i].push_back(res);
}
}
}
int getKthAncestor(int node, int k) {
if (k == 0) return node;
int l = -1, r = list[node].size() - 1;
while (l < r) {
int m = (l + r + 1) / 2;
if (k >= pow(2, m)) l = m;
else r = m - 1;
}
if (l == -1) return l;
return getKthAncestor(list[node][l], k - pow(2, l));
}
};
题解 2 - python
- 编辑时间：2023-06-12
- 执行用时：7080ms
- 内存消耗：48.2MB
- 编程语言：python
- 解法介绍：同上。
class TreeAncestor:
def __init__(self, n: int, parent: List[int]):
self.list = [[] for _ in range(n)]
for i in range(1, len(parent)):
self.list[i].append(parent[i])
j = res = 1
while res != -1:
res = self.getKthAncestor(i, pow(2, j))
if res != -1:
self.list[i].append(res)
j += 1
def getKthAncestor(self, node: int, k: int) -> int:
if k == 0:
return node
l = -1
r = len(self.list[node]) - 1
while l < r:
m = (l+r+1)//2
if k >= pow(2, m):
l = m
else:
r = m-1
if l == -1:
return l
return self.getKthAncestor(self.list[node][l], k-pow(2, l))
题解 3 - rust
- 编辑时间：2023-06-12
- 执行用时：204ms
- 内存消耗：34.9MB
- 编程语言：rust
- 解法介绍：同上。
struct TreeAncestor {
list: Vec<Vec<usize>>,
}
impl TreeAncestor {
fn new(n: i32, parent: Vec<i32>) -> Self {
let mut list = vec![vec![]; n as usize];
for i in 1..parent.len() {
list[i].push(parent[i] as usize);
let mut res = 1;
for j in 1.. {
res = TreeAncestor::_get_kth_ancestor(&list, i as i32, 2i32.pow(j as u32));
if res != -1 {
list[i].push(res as usize);
} else {
break;
}
}
}
Self { list }
}
fn _get_kth_ancestor(list: &Vec<Vec<usize>>, node: i32, k: i32) -> i32 {
if k == 0 {
node
} else {
let mut l = -1 as i32;
let mut r = (list[node as usize].len() - 1) as i32;
while l < r {
let m = (l + r + 1) / 2;
if k >= 2i32.pow(m as u32) {
l = m;
} else {
r = m - 1;
}
}
if l == -1 {
l
} else {
TreeAncestor::_get_kth_ancestor(list, list[node as usize][l as usize] as i32, k - (2i32.pow(l as u32)))
}
}
}
fn get_kth_ancestor(&self, node: i32, k: i32) -> i32 {
TreeAncestor::_get_kth_ancestor(&self.list, node, k)
}
}
题解 4 - cpp
- 编辑时间：2023-06-12
- 执行用时：392ms
- 内存消耗：132.1MB
- 编程语言：cpp
- 解法介绍：当前节点的第n项等于第n-1个父节点的第n-1项。
class TreeAncestor {
public:
vector<vector<int>> list;
TreeAncestor(int n, vector<int>& parent): list(vector<vector<int>>(n)) {
for (int i = 1; i < parent.size(); i++) {
list[i].push_back(parent[i]);
for (int j = 1; ; j++) {
if (list[list[i].back()].size() > j - 1) list[i].push_back(list[list[i].back()][j - 1]);
else break;
}
}
}
int getKthAncestor(int node, int k) {
if (k == 0) return node;
int l = -1, r = list[node].size() - 1;
while (l < r) {
int m = (l + r + 1) / 2;
if (k >= pow(2, m)) l = m;
else r = m - 1;
}
if (l == -1) return l;
return getKthAncestor(list[node][l], k - pow(2, l));
}
};
题解 5 - python
- 编辑时间：2024-04-06
- 执行用时：901ms
- 内存消耗：55.49MB
- 编程语言：python
- 解法介绍：倍增法。
class TreeAncestor:
def __init__(self, n: int, parents: List[int]):
self.parents = [[] for _ in range(n + 1)]
children = [[] for _ in range(n + 1)]
for i in range(n):
self.parents[i].append(parents[i])
children[parents[i]].append(i)
q = deque([0])
while q:
node = q.popleft()
for child in children[node]:
q.append(child)
arr = self.parents[node]
i = 1
while node and len(self.parents[arr[i - 1]]) > i - 1:
arr.append(self.parents[arr[i - 1]][i - 1])
i += 1
def getKthAncestor(self, node: int, k: int) -> int:
idx = 0
while pow(2, idx + 1) <= k: idx += 1
if len(self.parents[node]) <= idx: return -1
if pow(2, idx) == k: return self.parents[node][idx]
return self.getKthAncestor(self.parents[node][idx], k - pow(2, idx))