每日算法 — 使用java实现最近公共祖先：倍增预处理与Tarjan离线查询

最近公共祖先（Lowest Common Ancestor，简称 LCA）是树结构中最经典的问题之一。无论是操作系统中的文件目录层级、企业组织架构中的汇报关系，还是生物分类学中的物种演化树，LCA 都扮演着核心角色：给定树中两个节点，找到它们所有共同祖先中深度最大的那一个。本文将用 Java 完整实现两种主流解法——倍增法与 Tarjan 离线算法，从原理到代码逐一剖析。

一、问题建模与暴力解法

1.1 场景引入

想象一家公司的组织架构是一棵以 CEO 为根的有根树。若要查询”员工 A 和员工 B 的共同直属上司是谁”，本质上就是在求这两个节点在组织树中的最近公共祖先。类似场景还包括：

• 文件系统：两个文件的最近公共父目录
• 版本控制：Git 分支合并时的最近共同提交点
• 生物分类：两种生物在演化树上的最近共同祖先

1.2 形式化定义

给定一棵有根树 T（根节点编号为 1），以及两个节点 u 和 v，LCA(u, v) 是同时满足以下条件的节点 x：

1. x 是 u 的祖先，也是 v 的祖先
2. 在所有满足条件 1 的节点中，x 的深度最大（离根最远）

1.3 暴力解法：逐层上跳

最直观的思路是：先将较深的节点上跳到与另一节点同深度，然后两个节点同时逐层向上，直到相遇。

/**
 * 暴力LCA：逐层上跳
 * 时间复杂度：O(n) 单次查询，空间复杂度：O(n)
 */
public class NaiveLCA {
    // 树的邻接表表示
    List<Integer>[] tree;
    // 每个节点的父节点
    int[] parent;
    // 每个节点的深度（根节点深度为0）
    int[] depth;
    int n;

    public NaiveLCA(int n) {
        this.n = n;
        tree = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) tree[i] = new ArrayList<>();
        parent = new int[n + 1];
        depth = new int[n + 1];
    }

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

    /**
     * 从根节点开始DFS，预处理每个节点的父节点和深度
     * @param root 根节点编号
     */
    public void preprocess(int root) {
        Arrays.fill(depth, -1);
        dfs(root, 0, -1);
    }

    private void dfs(int u, int d, int p) {
        depth[u] = d;
        parent[u] = p;
        for (int v : tree[u]) {
            if (v != p) {
                dfs(v, d + 1, u);
            }
        }
    }

    /**
     * 查询u和v的最近公共祖先
     */
    public int query(int u, int v) {
        // 1. 将较深的节点上提至与另一节点同深度
        while (depth[u] > depth[v]) {
            u = parent[u];
        }
        while (depth[v] > depth[u]) {
            v = parent[v];
        }
        // 2. 同时上跳直到相遇
        while (u != v) {
            u = parent[u];
            v = parent[v];
        }
        return u;
    }
}

暴力法单次查询最坏需要 O(n) 时间（如一条链状树）。若查询次数 q 很大，总复杂度将达到 O(nq)，难以接受。下面的两种优化方法将其分别降到 O(n log n + q log n) 和 O(n + q α(n))。

二、核心算法一：倍增法（Binary Lifting）

2.1 核心思想

倍增法的精髓在于预处理跳跃表。对于每个节点 u，我们记录它向上跳 2^k 步后的祖先节点，记为 up[u][k]。借助二进制分解的思想，任意步数的上跳都可以由若干 2 的幂次组合而成，从而将逐层上跳的线性过程优化为对数过程。

2.2 预处理递推

up[u][0] = parent[u]（向上跳 1 步即父节点）
up[u][k] = up[ up[u][k-1] ][k-1]（向上跳 2^k 步 = 先跳 2^{k-1} 步，再跳 2^{k-1} 步）

预处理需要 O(n log n) 时间和空间。

2.3 查询过程

1. 深度对齐：利用 up 表将较深的节点快速上提到与另一节点同深度
2. 同步上跳：从高到低枚举 k，若 up[u][k] != up[v][k]，则同时上跳 2^k 步
3. 返回父节点：此时 u 和 v 的父节点即为 LCA

单次查询时间 O(log n)。

import java.util.*;

/**
 * 倍增法LCA
 * 预处理：O(n log n)，单次查询：O(log n)
 */
public class BinaryLiftingLCA {
    List<Integer>[] tree;
    // up[u][k] 表示节点u向上跳2^k步到达的祖先
    int[][] up;
    int[] depth;
    int n;
    int LOG; // 最大层数，满足 2^LOG >= n

    public BinaryLiftingLCA(int n) {
        this.n = n;
        tree = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) tree[i] = new ArrayList<>();
        // LOG取ceil(log2(n)) + 1，确保覆盖所有可能步数
        LOG = 32 - Integer.numberOfLeadingZeros(n) + 1;
        up = new int[n + 1][LOG];
        depth = new int[n + 1];
    }

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

    /**
     * 从根节点开始DFS，同时构建up表
     */
    public void preprocess(int root) {
        Arrays.fill(depth, -1);
        dfs(root, 0, -1);
    }

    private void dfs(int u, int d, int p) {
        depth[u] = d;
        up[u][0] = p; // 2^0 = 1步的祖先即父节点
        // 递推计算up[u][k]
        for (int k = 1; k < LOG; k++) {
            int mid = up[u][k - 1];
            up[u][k] = (mid == -1) ? -1 : up[mid][k - 1];
        }
        for (int v : tree[u]) {
            if (v != p) {
                dfs(v, d + 1, u);
            }
        }
    }

    /**
     * 将节点u向上提升target步
     * @param u 起始节点
     * @param target 需要上跳的步数
     * @return 提升后的节点
     */
    private int liftNode(int u, int target) {
        for (int k = 0; k < LOG; k++) {
            // 若target的第k位为1，则上跳2^k步
            if ((target & (1 << k)) != 0) {
                u = up[u][k];
                if (u == -1) break; // 已到达根节点上方
            }
        }
        return u;
    }

    /**
     * 查询u和v的LCA
     */
    public int query(int u, int v) {
        // 1. 确保u是较深的节点
        if (depth[u] < depth[v]) {
            int tmp = u; u = v; v = tmp;
        }
        // 2. 将u上提到与v同深度
        int diff = depth[u] - depth[v];
        u = liftNode(u, diff);

        // 3. 若此时已相等，直接返回
        if (u == v) return u;

        // 4. 从高到低枚举k，同步上跳
        for (int k = LOG - 1; k >= 0; k--) {
            if (up[u][k] != -1 && up[u][k] != up[v][k]) {
                u = up[u][k];
                v = up[v][k];
            }
        }
        // 5. 此时u和v的父节点即为LCA
        return up[u][0];
    }
}

2.4 复杂度分析

三、核心算法二：Tarjan 离线算法

3.1 离线 vs 在线

倍增法属于在线算法（Online），即查询可以动态到达、立即回答。而 Tarjan 算法属于离线算法（Offline），需要预先知道所有查询，在一次 DFS 遍历中批量处理完毕。

3.2 核心思想：并查集 + DFS

Tarjan 算法的巧妙之处在于利用并查集（Union-Find）维护已遍历子树的”代表节点”。DFS 遍历树时，当某棵子树完全遍历完毕后，将其所有节点合并到根节点所在的集合。对于每个查询 (u, v)，当 u 的子树遍历完成且此时 v 已被访问（或反之），则 v 所在集合的代表节点即为 LCA(u, v)。

3.3 算法流程

1. 从根节点开始 DFS
2. 遍历子节点，递归处理每棵子树
3. 子树递归返回后，将子节点与当前节点在并查集中合并
4. 处理所有与当前节点相关的查询：若查询的另一节点已被访问，则答案为另一节点在并查集中的代表节点
5. 标记当前节点为”已处理”

import java.util.*;

/**
 * Tarjan离线LCA算法
 * 时间复杂度：O(n + q × α(n))，其中α为阿克曼函数的反函数，可视为常数
 * 空间复杂度：O(n + q)
 */
public class TarjanLCA {
    List<Integer>[] tree;
    // 并查集父节点数组
    int[] dsuParent;
    // 并查集代表节点（集合的根）
    int[] ancestor;
    // 标记节点是否已遍历完毕
    boolean[] visited;
    // 标记节点是否已被访问（在DFS路径上）
    boolean[] onPath;
    int n;

    // 查询结构：存储所有查询及其索引，便于批量输出
    List<Query>[] queries;
    int[] answer;

    public TarjanLCA(int n) {
        this.n = n;
        tree = new ArrayList[n + 1];
        queries = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
            queries[i] = new ArrayList<>();
        }
        dsuParent = new int[n + 1];
        ancestor = new int[n + 1];
        visited = new boolean[n + 1];
        onPath = new boolean[n + 1];
    }

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

    /**
     * 添加查询，由于LCA(u,v)=LCA(v,u)，存储为双向
     * @param idx 查询的原始索引
     * @param u 节点u
     * @param v 节点v
     */
    public void addQuery(int idx, int u, int v) {
        queries[u].add(new Query(idx, v));
        queries[v].add(new Query(idx, u));
    }

    /**
     * 执行Tarjan离线LCA计算
     * @param root 树的根节点
     * @param q 查询总数
     * @return 每个查询的答案数组
     */
    public int[] solve(int root, int q) {
        answer = new int[q];
        // 初始化并查集
        for (int i = 1; i <= n; i++) {
            dsuParent[i] = i;
            ancestor[i] = i;
        }
        tarjanDFS(root, -1);
        return answer;
    }

    private void tarjanDFS(int u, int parent) {
        onPath[u] = true;

        // 递归处理所有子节点
        for (int v : tree[u]) {
            if (v == parent) continue;
            tarjanDFS(v, u);
            // 子树遍历完毕，将子节点合并到当前节点
            union(u, v);
            // 合并后，当前集合的代表祖先更新为u
            ancestor[find(u)] = u;
        }

        visited[u] = true;

        // 处理所有与u相关的查询
        for (Query q : queries[u]) {
            int v = q.node;
            if (visited[v]) {
                // v已遍历完毕，其所在集合的代表祖先即为LCA
                answer[q.idx] = ancestor[find(v)];
            }
        }

        onPath[u] = false;
    }

    // 并查集查找（带路径压缩）
    private int find(int x) {
        if (dsuParent[x] != x) {
            dsuParent[x] = find(dsuParent[x]);
        }
        return dsuParent[x];
    }

    // 并查集合并
    private void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            dsuParent[fy] = fx;
        }
    }

    // 查询内部类
    static class Query {
        int idx;   // 查询索引
        int node;  // 查询的另一节点
        Query(int idx, int node) {
            this.idx = idx;
            this.node = node;
        }
    }
}

3.4 正确性直觉

为什么 ancestor[find(v)] 就是 LCA(u, v)？关键在于 DFS 的完成顺序：

• 当处理节点 u 时，若 v 已被标记为 visited，说明 v 所在的整棵子树已经完全遍历
• 此时 v 在并查集中所在的集合，恰好包含了所有以 v 为根且已被遍历完毕的子树
• 这个集合的代表祖先 ancestor[find(v)]，就是 v 向上追溯到的、当前仍在 DFS 递归栈中的最近祖先——即 u 和 v 的最近公共祖先

3.5 复杂度分析

四、两种算法的对比与选型

实际工程中，若查询是交互式的（如用户实时点击查询），选倍增法；若查询可以预先收集（如批量数据分析），Tarjan 离线算法在常数因子和空间占用上均更有优势。

五、完整运行示例

以下将两种算法整合到一个可运行的示例中，以一棵 9 节点的树验证正确性：

public class LCADemo {
    public static void main(String[] args) {
        int n = 9;
        int[][] edges = {
            {1, 2}, {1, 3}, {2, 4}, {2, 5},
            {3, 6}, {3, 7}, {5, 8}, {5, 9}
        };

        // 测试倍增法
        BinaryLiftingLCA bl = new BinaryLiftingLCA(n);
        for (int[] e : edges) bl.addEdge(e[0], e[1]);
        bl.preprocess(1);

        System.out.println("=== 倍增法查询结果 ===");
        System.out.println("LCA(4, 5) = " + bl.query(4, 5)); // 期望 2
        System.out.println("LCA(4, 8) = " + bl.query(4, 8)); // 期望 2
        System.out.println("LCA(6, 7) = " + bl.query(6, 7)); // 期望 3
        System.out.println("LCA(8, 9) = " + bl.query(8, 9)); // 期望 5
        System.out.println("LCA(4, 6) = " + bl.query(4, 6)); // 期望 1

        // 测试Tarjan离线算法
        TarjanLCA tarjan = new TarjanLCA(n);
        for (int[] e : edges) tarjan.addEdge(e[0], e[1]);
        // 添加与倍增法相同的查询
        tarjan.addQuery(0, 4, 5);
        tarjan.addQuery(1, 4, 8);
        tarjan.addQuery(2, 6, 7);
        tarjan.addQuery(3, 8, 9);
        tarjan.addQuery(4, 4, 6);

        int[] ans = tarjan.solve(1, 5);
        System.out.println("\n=== Tarjan离线算法查询结果 ===");
        System.out.println("LCA(4, 5) = " + ans[0]); // 期望 2
        System.out.println("LCA(4, 8) = " + ans[1]); // 期望 2
        System.out.println("LCA(6, 7) = " + ans[2]); // 期望 3
        System.out.println("LCA(8, 9) = " + ans[3]); // 期望 5
        System.out.println("LCA(4, 6) = " + ans[4]); // 期望 1
    }
}

运行结果：

=== 倍增法查询结果 ===
LCA(4, 5) = 2
LCA(4, 8) = 2
LCA(6, 7) = 3
LCA(8, 9) = 5
LCA(4, 6) = 1

=== Tarjan离线算法查询结果 ===
LCA(4, 5) = 2
LCA(4, 8) = 2
LCA(6, 7) = 3
LCA(8, 9) = 5
LCA(4, 6) = 1

六、扩展应用

6.1 LCA 与树上路径问题

LCA 是求解树上任意两点间路径的基石。路径 u → v 的长度可以表示为：

dist(u, v) = depth[u] + depth[v] - 2 × depth[LCA(u, v)]

基于此，树上路径求和、路径最值、路径更新等问题都可以通过 LCA 转化为从根出发的路径问题。

6.2 LCA 与 RMQ 的等价性

倍增法本质上利用了 RMQ（区间最值查询） 的思想——通过预处理将查询降为对数级。事实上，LCA 问题与 RMQ 问题在特定条件下可以互相转化（通过欧拉序 + 线段树/Sparse Table），这也是算法设计中”问题转化”思想的典型体现。

6.3 动态 LCA

当树结构发生变化（节点增删、边增删）时，静态 LCA 算法需要重新预处理。Link-Cut Tree（LCT） 是一种支持动态树操作的先进数据结构，可以在 O(log n) 时间内完成动态 LCA 查询，是更高级的主题延伸方向。

七、总结

本文围绕最近公共祖先这一树论核心问题，完整实现了两种经典解法：

• 倍增法通过 O(n log n) 预处理构建跳跃表，实现 O(log n) 单次在线查询，代码直观、易于理解，是面试和竞赛中的首选方案。
• Tarjan 离线算法巧妙结合 DFS 与并查集，以 O(n + q) 的总复杂度批量处理所有查询，在查询量巨大的离线场景中展现出极致效率。

两种方法从”空间换时间”和”离线批量处理”两个不同维度切入，展示了算法设计中”预处理策略”与”问题转化思想”的强大威力。