最近公共祖先-算法学习

问题提出

• 如何计算树上任意两点 x 和 y 的最近公共祖先 呢？

• 通俗地理解-假设在一棵二叉树中，有两个节点 和
• 那么该如何求这两个节点的最近公共祖先节点
• 如下图，节点 和节点的最近公共祖先节点是

思路解析

1. 假设一个节点的深度为，这可以通过一次 DFS 预处理出来。

1. 那么这里如何进行预处理呢？
2. 单纯找一个节点的深度的解决办法较为简单

2. 假设(否则交换两个节点的位置)
3. 可以先把更靠下的更新为第个祖先节点，这样和就处于同一深度了

1. 这一句话还不理解，然后怎么理解呢？
2. 如图 图-Tree1 节点的深度是，节点的深度是
3. 那么就把更靠下的更新为其第个祖先节点节点，也就是节点

4. 如果此时，那么就是

1. 这里意思是如果节点更新之后等于节点那么这两个节点的公共节点就是
2. 否则说明在更上面，那么就把和一起往上跳

5. 由于不知道的具体位置，只能不断尝试，先尝试大步跳，再尝试小步跳。
6. 设（表示对 以 2 为底 n 的对数进行向下取整），循环直到
7. 每次循环逻辑如下

1. 如果的第个祖先节点不存在，即，说明步子迈大了，将减 1，继续循环
2. 如果的第个祖先节点存在，且。说明在的上面

1. 那么更新，将减然后继续循环

3. 若，那么可能在的下面，由于无法向下跳，只能将减，然后继续循环

8. 循环结束的时候，与只有一步之遥，即

1. 是如何得出该结论的？

• 以寻找节点和节点的最近公共祖先节点为例

• 那么首先更新更深的节点为从而保证了和节点位于相同的深度

然后开始向上寻找，这里假设树或者图一共有个节点，那么极端情况下，最底层的节点的第个祖先节点是根节点

又因为一个正整数可以写成若干个 2 次幂数的和，即寻找一个节点的祖先节点的时候，可以依次寻找其第个祖先节点

ex：，即寻找一个节点的第13个祖先节点，可以依次寻找第个祖先节点即可。

• 所以这里有 ，向下取整是因为节点本身需要被忽略
• 以图示为例，这里可以计算得出
• 这里设

• 那么很显然最开始的第个祖先节点不存在
• ，第个祖先节点也不存在，继续
• 直到，则的第个祖先节点是节点

• 那么此时对于而言，其第个祖先节点相同。但是暂时不确定是不是最近的公共祖先节点

• 所以 继续 ，此时需要找到节点的第个公共节点分别是
• 此时满足，则更新，然后更新
• 此时寻找的第个祖先节点分别是，然后更新
• 此时退出循环。则最近公共祖先节点--

思路总结

1. 总的来说，寻找祖先节点，需要使用二维数组来缓存节点的祖先节点。
2. 然后利用方法来寻找公共组建节点，降低查找次数

代码实现

• 通常入参是 二维数组的形式，然后利用来建图

class TreeAncestor {

    // 缓存公共祖先节点
    private int[][] cache;
    private int[] depth;

    public TreeAncestor(int[][] edges) {
        int n = edges.length - 1;
        int m = 32 - Integer.numberOfLeadingZeros(n);
        // 使用 List 数组表示 邻接表
        List<Integer> g[] = new ArrayList[];
        // 初始化数组元素
        Arrays.setAll(g, e -> new ArrayList<>());
        // 遍历节点
        for(int[] edge : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        depth = new int[n];
        cache = new int[n][m];
        
        dfs(g, 0, -1);

        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 : pa[p][i];
            }
        }
    }

    private void dfs(List<Integer>[] g, int x, int fa) {
        cache[x][0] = fa;
        for (int y : g[x]) {
            if (y != fa) {
                depth[y] = depth[x] + 1;
                dfs(g, y, x);
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        for (; k > 0; k &= k - 1)
            node = cache[node][Integer.numberOfTrailingZeros(k)];
        return node;
    }

    public int getLCA(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = y;
            y = x;
            x = tmp;
        }
        // 使 y 和 x 在同一深度
        y = getKthAncestor(y, depth[y] - depth[x]);
        if (y == x)
            return x;
        for (int i = cache[x].length - 1; i >= 0; i--) {
            int px = cache[x][i], py = pa[y][i];
            if (px != py) {
                x = px;
                y = py;
            }
        }
        return cache[x][0];
    }

    
}

参考

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