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;
    }
};
最后修改:2020 年 06 月 14 日 10 : 20 PM
如果觉得我的文章对你有用,请随意赞赏