1483. 树节点的第 K 个祖先

LC每日一题，参考1483. 树节点的第 K 个祖先。

题目

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
实现 TreeAncestor 类：

• TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
• getKthAncestor(int node, int k) 返回节点 node 的第 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 因为不存在满足要求的祖先节点

解题思路

• 倍增+动态规划：查询函数参数有两个,使用空间n*n存储查询结果会超出题目要求内存,使用倍增思想优化二维空间到M(2^M>50000,50000为给定用例n的最大值),动态规划转移方程ans[i][j] = ans[ans[i][j-1]][j-1]。

倍增+动态规划

class TreeAncestor {
    int[][] ans;
    int M;
    public TreeAncestor(int n, int[] parent) {
        //由于超内存 需要使用倍增表 
        //倍增:第二维j则k=2^j 对于每个k可进行二进制分解为2^k1+2^k2+..
        //比如k=13=1101(2)=2^3+2^2+2^0->找0找2找3的对应父节点
        //确定第二维j最大值
        M = 50000&(-50000);
        //while(Math.pow(2,M) < 50000) M++;
        ans = new int[n+1][M];
        for(int i = 0; i < n; i++) {
            ans[i][0] = parent[i];//k=2^0=1
        }
        //动态规划 2进制两倍关系
        for(int i = 0; i < n; i++) {
            for(int j = 1; j < M; j++) {
                //2^j=2^j-1 + 2^j-1
                if(ans[i][j-1] != -1) ans[i][j] = ans[ans[i][j-1]][j-1];
                else ans[i][j] = -1;
            }
        }
    }
    
    public int getKthAncestor(int node, int k) {
        for(int i = 0; i < M; i++) {
            if(((k>>i)&1) == 1) {
                if(node == -1) return -1;
                node = ans[node][i];
            }
        }
        return node;
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，TreeAncestor函数中总共遍历n*M次,n为树节点数,M为logn, getKthAncestor函数最多调用n次,每次时间M所以时间复杂度为T(2nlogn) = O(nlogn)。
• 空间复杂度：O(nlogn)，ans数组使用nlogn的存储空间。