最近公共祖先-算法学习

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];
    }

    
}