1483. 树节点的第 K 个祖先 又学了一招

1483. 树节点的第 K 个祖先

最开始自己的思路竟然是想构建多叉树，这样实在太蠢了，还是直接学习优秀的官解吧。

学习历程

暴力解法学习

1. 举例说明：n = 7 parent = [-1, 0, 0, 1, 1, 2, 2]
2. 一共七个节点 节点的值分别是：0，1，2，3，4，5，6

1. -1：表示根节点
2. ex：寻找节点6的祖先节点

1. 第一个祖先节点：parent[6] = 2
2. 第二个祖先节点：parent[2] = 0
3. 第三个祖先节点：parent[0] = -1 -1 不存在，所以不存在第三个祖先节点

3. 此解法时间复杂度O(k)，果不其然超时了

class TreeAncestor {

    private int[] parent;


    public TreeAncestor(int n, int[] parent) {
        this.parent = parent;
    }
    
    public int getKthAncestor(int node, int k) {
        int cnt = 0;
        if(cnt == k) {
            return cnt;
        }
        while (node != -1) {
            node = parent[node];
            cnt++;
            if(cnt == k) {
                return node;
            }
        }
        return -1;
    }
}

优化暴力算法

1. 预处理节点？需要预处理出哪些节点？----算了，想不起来，直接往下看
2. 预处理出每一个节点的第个祖先节点，即第 2、4、6、8......个祖先节点

1. ex：一个节点 node 的第一个祖先节点是 parent[node]
2. ？？？还是看不懂，继续往下

3. 任意 k 可以分解为若干不同的 2 的幂，ex：13 = 8 + 4 + 1
4. 所以只需要预处理出这些 祖先节点，就可以快速地到达任意第 k 个祖先节点。

1. 看到这里明白了一些，但是如何处理？继续往下看

5. ex：

1. 所以，可以先往上跳 8步、4步 最后 1 步。也可以 4->8->1 或者 1->8->4
2. 无论如何只需要三次就能找到目标第13个祖先节点

如何实现该算法

1. 在构造函数TreeAncestor中，预处理出每一个节点x的第个祖先节点，记作

1. 若第个祖先节点不存在，则

2. 计算方式如下

1. 先枚举i，再枚举x。ex：cache[x][0]表示节点x的第个祖先节点，所以有

1. cache[x][0] = parent[x]
2. cache[x][1]：表示节点x的第个祖先节点->cache[x][1] = cache[cache[x][0]][0]

1. 解释：求节点x的第 2 个祖先节点
2. 其第一个祖先节点是parent[x],相当于求parent[x]的祖先节点，即parent[parent[x]]
3. 等同于求cache[parent[parent[x]]][0]
4. 又因为parent[x] = cache[x][0]
5. 所以有cache[x][1] = cache[cache[x][0][0]

3. 我丢--真的太妙了

2. 那么可以推导出cache[x][i+1] = cache[cache[x][i]][i]

1. 如果cache[x][i] = -1则cache[x][i+1] = -1

3. 对于i+1而言最多为

1. ex：当,
2. 意味着最多需要预处理个祖先节点

3. 构造函数预处理

1. 首先要考虑对于参数 n，最多需要预处理多少个节点
2. 即如何求i

private int[][] cache;

public TreeAncestor(int n, int[] parent) {
    //  numberOfLeadingZeros 计算 数字 n 对应的二进制数的长度
    int m = 32 - Integer.numberOfLeadingZeros(n);
    // 这里对于数字 1->n 分别预处理其 2^(0->m) 个节点的数据
    cache = new int[n][m];
    for(int i = 0;i < n;i++) {
        cache[i][0] = parent[i];
    }
    for(int i = 0;i < m - 1;i++) {
        for(int x = 0;x < n;x++) {
            int p = cache[x][i];
            cache[x][i + 1] = p < 0?-1:cache[p][i];
        }
    }
}

4. 寻找第 k 个祖先节点

1. getKthAncestor

public int getKthAncestor(int node, int k) {
    int m = 32 - Integer.numberOfLeadingZeros(k);
    for(int i = 0;i < m;i++) {
        if(((k >> i) & 1) == 1) {
            node = cache[node][i];
            if(node < 0) {
                break;
            }
        }
    }
    return node;
}

b. 另一种写法

public int getKthAncestor(int node, int k) {
    //  这里不断去去掉 k 最低位的 1
    //  相当于  1  4  8 这样跳
    for(;k > 0 && node != -1;k &= k - 1) {
        node = cache[node][Integer.numberOfTrailingOfZeros(k)];
    }
    return node;
}

• 真是太妙了

参考

https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/solution/mo-ban-jiang-jie-shu-shang-bei-zeng-suan-v3rw/

完结撒花，又学了一招