2023-06-12每日一题
一、题目编号
1483. 树节点的第 K 个祖先
二、题目链接
点击跳转到题目位置
三、题目描述
给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
实现 TreeAncestor 类:文章来源:https://www.toymoban.com/news/detail-479981.html
- TreeAncestor(int n, int[] parent) 对树和父数组中的节点数初始化对象。
- getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点,返回 -1 。
提示:文章来源地址https://www.toymoban.com/news/detail-479981.html
- 1 <= k <= n <= 5 * 104
- parent[0] == -1 表示编号为 0 的节点是根节点。
- 对于所有的 0 < i < n ,0 <= parent[i] < n 总成立
- 0 <= node < n
- 至多查询 5 * 104 次
四、解题代码
class TreeAncestor {
public:
const int Log = 16;
vector<vector<int>> ancestors;
TreeAncestor(int n, vector<int>& parent) {
ancestors = vector<vector<int>>(n, vector<int>(Log, -1));
for (int i = 0; i < n; ++i) {
ancestors[i][0] = parent[i];
}
for (int j = 1; j < Log; ++j) {
for (int i = 0; i < n; i++) {
if (ancestors[i][j - 1] != -1) {
ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
}
}
}
}
int getKthAncestor(int node, int k) {
for (int j = 0; j < Log; j++) {
if ((k >> j) & 1) {
node = ancestors[node][j];
if (node == -1) {
return -1;
}
}
}
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);
*/
五、解题思路
到了这里,关于2023-06-12 LeetCode每日一题(树节点的第 K 个祖先)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!