1483. 树节点的第 K 个祖先 (opens new window)

1.二叉树倍增

分析：使用二进制思想保存每个节点的所有祖先，从而查找的时间复杂度O(log n)，并且保存祖先节点时，开辟的空间大小为O(n*log n)。倍增算法和二分法复杂度类似，但是两者之间是完全相反的算法，二分法每次都会缩小一半，而倍增法每次都会扩大一倍。

定义祖先数组ancestors[ i ][ j ]为第i个节点的第2^j个祖先节点的标号。

状态转移公式为ancestors【 i 】【 j 】=ancestors【ancestors[i][j-1]】【j-1】，表示第i个节点的第2^j个祖先，等于第i个节点的第2^(j-1)个祖先的第2^(j-1)个祖先。

查找：查找第k个祖先时，只需要找到k的二进制表示中为1的位置，然后映射到祖先倍增数组的索引下标进行查找。具体来说如果要找第5个祖先，依次查找当前节点第1个祖先，第4个祖先。通过移位运算和与运算，找到当前祖先代数二进制表示为1的位置，将线性运算转化为在祖先数组上的二进制数级的运算。

class TreeAncestor {
    int[][] ancestors;
    static final int LOG = 16;
    public TreeAncestor(int n, int[] parent) {
        ancestors=new int[n][LOG];
        for(int j=0;j<16;j++){
            for(int i=0;i<n;i++){
                if(j==0)  ancestors[i][j]=parent[i];
                else{
                    int node=ancestors[i][j-1];
                    ancestors[i][j]=node!=-1?ancestors[node][j-1]:-1;
                }
            }
        }
    }
    public int getKthAncestor(int node, int k) {
        for (int j = 0; j < LOG; j++) {
            if (((k >> j) & 1) != 0) {
                node = ancestors[node][j];
                if (node == -1) {
                    return -1;
                }
            }
        }
        return node;
    }
}