周赛 – 193 – 树节点的第 K 个祖先

4. 树节点的第 K 个组先

给你一棵树,树上有 n 个节点,按从 0n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
请你设计并实现 getKthAncestor(int node, int k) 函数,函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点,返回 -1
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

样例

示例 1:

输入:
[“TreeAncestor”,”getKthAncestor”,”getKthAncestor”,”getKthAncestor”]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]
输出:
[null,1,0,-1]
解释:
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);
treeAncestor.getKthAncestor(3, 1); // 返回 1 ,它是 3 的父节点
treeAncestor.getKthAncestor(5, 2); // 返回 0 ,它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点

提示

  • 1 <= k <= n <= 5*10^4
  • parent[0] == -1 表示编号为 0 的节点是根节点。
  • 对于所有的 0 < i < n0 <= parent[i] < n 总成立
  • 0 <= node < n
  • 至多查询 5*10^4

思路

看到数据范围暴力是肯定不行的(虽然大家都暴力过了。这涉及到我的芝士盲区(虽然本质也是DP。

使用 dp[i][j] 记录结点 i 的第 2 ^ j 个祖先。初始化的时候,先初始化每个结点的第 2 ^ 0 = 1 个祖先,再利用已经求好的第 1 个祖先去求 2 ^ 1 = 2 个,再利用第 2 个祖先求第 4 个,以此类推。查询时,利用二进制分解的性质即可。

题解

int fa[50005][22];
class TreeAncestor {
public:
    TreeAncestor(int n, vector<int>& parent) {
        for(int i=0; i<n; i++) fa[i][0] = parent[i];
        
        for(int i=1; i<=20; i++) {
            for(int j=0; j<n; j++) {
                if(fa[j][i-1] == -1) fa[j][i] = -1;
                else fa[j][i] = fa[fa[j][i-1]][i-1];
            }
        }
    }
    
    int getKthAncestor(int node, int k) {
        for(int i=20; i>=0; i--) {
            if(node != -1 && k >= (1<<i)) {
                node = fa[node][i];
                k -= (1<<i);
            }
        }
        return node;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇