每日算法 — 使用java实现LCA最近公共祖先：倍增算法与RMQ预处理

算法背景

最近公共祖先（Lowest Common Ancestor，LCA）问题是树结构算法中的经典问题：给定一棵有根树和两个节点 u、v，找出它们的所有公共祖先中深度最大的那个。LCA 是许多复杂算法的基础模块，应用于树的距离查询、网络路由、版本控制系统（如 Git 的合并基础查找）以及生物信息学的物种演化分析。

核心思想

倍增法是求解 LCA 最常用的高效算法。预处理阶段，为每个节点记录其向上第 2^k 代祖先 up[k][v]；查询时，先将两个节点提升到同一深度，然后同时向上倍增跳跃，直到找到 LCA。

另一种思路是将 LCA 转化为 RMQ（区间最值查询）问题：通过欧拉序遍历将树展平为数组，LCA 即为该数组上某区间的深度最小值，可通过 Sparse Table 实现 O(1) 查询。

完整Java实现

import java.util.*;

public class LCAFinder {

    private int n;                      // 节点数
    private int LOG;                    // 最大倍增层数
    private List<Integer>[] tree;       // 邻接表
    private int[][] up;                 // up[k][v]: v向上2^k的祖先
    private int[] depth;                // 节点深度
    private int[] parent;               // 直接父节点

    @SuppressWarnings("unchecked")
    public LCAFinder(int n) {
        this.n = n;
        this.LOG = 32 - Integer.numberOfLeadingZeros(n);
        tree = new ArrayList[n];
        for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
        up = new int[LOG][n];
        depth = new int[n];
        parent = new int[n];
        Arrays.fill(parent, -1);
    }

    public void addEdge(int u, int v) {
        tree[u].add(v);
        tree[v].add(u);
    }

    /**
     * 以root为根进行DFS，预处理深度和up表
     */
    public void preprocess(int root) {
        // BFS/DFS初始化第一层祖先
        Arrays.fill(depth, -1);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(root);
        depth[root] = 0;
        up[0][root] = root; // 根节点的祖先是自身

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : tree[u]) {
                if (depth[v] == -1) {
                    depth[v] = depth[u] + 1;
                    parent[v] = u;
                    up[0][v] = u;
                    queue.add(v);
                }
            }
        }

        // 倍增预处理：up[k][v] = up[k-1][ up[k-1][v] ]
        for (int k = 1; k < LOG; k++) {
            for (int v = 0; v < n; v++) {
                up[k][v] = up[k - 1][up[k - 1][v]];
            }
        }
    }

    /**
     * 将节点u向上提升step层
     */
    private int liftNode(int u, int step) {
        for (int k = 0; k < LOG; k++) {
            if ((step & (1 << k)) != 0) {
                u = up[k][u];
            }
        }
        return u;
    }

    /**
     * 查询u和v的最近公共祖先，时间复杂度O(log n)
     */
    public int query(int u, int v) {
        if (depth[u] < depth[v]) {
            int tmp = u; u = v; v = tmp;
        }
        // 将u提升到与v同一深度
        u = liftNode(u, depth[u] - depth[v]);

        if (u == v) return u;

        // 同时向上倍增跳跃
        for (int k = LOG - 1; k >= 0; k--) {
            if (up[k][u] != up[k][v]) {
                u = up[k][u];
                v = up[k][v];
            }
        }

        // 此时u和v的直接父节点就是LCA
        return up[0][u];
    }

    /**
     * 计算u到v的路径长度（边数）
     */
    public int distance(int u, int v) {
        int lca = query(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }

    /**
     * 获取从u到v的路径上的所有节点
     */
    public List<Integer> getPath(int u, int v) {
        List<Integer> path = new ArrayList<>();
        int lca = query(u, v);

        // u到LCA的路径
        while (u != lca) {
            path.add(u);
            u = parent[u];
        }
        path.add(lca);

        // v到LCA的路径（需要反转）
        List<Integer> right = new ArrayList<>();
        while (v != lca) {
            right.add(v);
            v = parent[v];
        }
        Collections.reverse(right);
        path.addAll(right);

        return path;
    }

    public static void main(String[] args) {
        /*
         * 构建如下树结构（0为根）：
         *        0
         *      / | \
         *     1  2  3
         *    / \    |
         *   4   5   6
         *  /
         * 7
         */
        LCAFinder lca = new LCAFinder(8);
        lca.addEdge(0, 1);
        lca.addEdge(0, 2);
        lca.addEdge(0, 3);
        lca.addEdge(1, 4);
        lca.addEdge(1, 5);
        lca.addEdge(3, 6);
        lca.addEdge(4, 7);
        lca.preprocess(0);

        System.out.println("LCA(7, 5) = " + lca.query(7, 5)); // 1
        System.out.println("LCA(7, 6) = " + lca.query(7, 6)); // 0
        System.out.println("LCA(4, 7) = " + lca.query(4, 7)); // 4
        System.out.println("LCA(2, 6) = " + lca.query(2, 6)); // 0

        System.out.println("\\ndistance(7, 6) = " + lca.distance(7, 6)); // 4
        System.out.println("distance(7, 5) = " + lca.distance(7, 5)); // 3

        System.out.println("\\npath(7, 6) = " + lca.getPath(7, 6));
        System.out.println("path(7, 5) = " + lca.getPath(7, 5));
    }
}

复杂度分析

预处理：BFS 遍历 O(n)，倍增表构建 O(n log n)。
单次查询：O(log n) 时间。
空间：O(n log n) 存储倍增表。
优化：若使用 RMQ + 欧拉序 + Sparse Table，查询可优化到 O(1)，但预处理空间增至 O(n log n)。

应用场景

LCA 在社交网络的好友关系分析、文件系统的目录结构查询、版本控制系统的分支合并、生物信息学的进化树分析中都有广泛应用。倍增法的思想（将线性跳跃转化为二进制幂次组合）也是许多高级算法的通用技巧，如快速幂、树上差分和重链剖分。

Tagged with: LCA 倍增算法最近公共祖先树算法