最近公共祖先 (LCA)

Published: Sun Feb 15 2026 | Modified: Sat Feb 07 2026 , 4 minutes reading.

LCA：历史的调停者

算法背后的故事：Git 的合并冲突

想象你正在开发一个软件项目。

Alice 在周一从 main 分支切出这了一个新功能分支。
Bob 在周二从 main 分支切出了一个修复分支。
周五，他们都试图把代码合并回去。

Git 慌了。为了智能地合并他们的修改，Git 必须找到 Alice 和 Bob 开始分道扬镳的那个确切的历史快照。这个快照就是 基准提交 (Base Commit)。

在计算机科学中，这个“基准提交”就是 最近公共祖先 (LCA)。它是树中同时作为两个节点祖先的最深节点。高效地找到它，是调解分歧的关键。

为什么需要它？

LCA 是处理 层级结构 的基础工具。

版本控制 (Git)： 寻找三路合并 (3-way merge) 的基准点。
生物学： 寻找人类和黑猩猩最近的共同祖先。
社交网络： “我们是什么亲戚？”（寻找最近的共同长辈）。
前端 DOM： 确定两个 HTML 元素最近的共同父容器。

算法是如何“思考”的 (倍增法)

朴素的方法很简单：Alice 往上走到根节点，标记每一步。然后 Bob 往上走，遇到的第一个带标记的节点就是 LCA。但这太慢了，如果树很深，复杂度是 $O(N)$ 。

聪明的方法是 倍增法 (Binary Lifting)。它让我们能够穿越时间。

预计算 (时间机器)： 每个节点不只记住“谁是我爸爸”（向上 1 步），而是记住了：
- 我的爸爸（向上 $2^0$ 步）
- 我的爷爷（向上 $2^1$ 步）
- 我的太爷爷的爸爸（向上 $2^2$ 步）
- …以此类推（向上 $2^k$ 步）。
对齐： 如果 Alice 在树中的位置比 Bob 深，她利用“2 的幂次”跳跃，快速升到和 Bob 同以高度。
共同跳跃： 现在他们在同一高度了。他们一起尝试向上跳。他们尝试尽可能大的跳跃（比如 16 步），前提是跳完之后不能到达同一个点。如果跳 16 步会撞到一起，说明跳得太远了（越过了 LCA）。所以他们尝试小一点的跳跃（8 步）。
他们不断重复这个过程，直到他们恰好位于 LCA 的 下方一步。最后，再向上走一小步，他们就相遇了。

工程决策：用空间换时间

倍增法是 时空权衡 (Space-Time Tradeoff) 的经典案例。

我们消耗 $O(N \log N)$ 的空间来存储跳跃表。
我们换取了 $O(\log N)$ 的极速查询。

对于一棵有 100 万个节点的树，朴素搜索可能需要 100 万步。倍增法只需要约 20 步。这就是对数的魔力。

实现参考 (Python)

import math

class LCASolver:
    def __init__(self, n, adj, root=0):
        self.n = n
        self.level = [0] * n
        self.LOG = math.ceil(math.log2(n))
        # up[i][j] 表示节点 i 向上跳 2^j 步到达的祖先
        self.up = [[-1] * self.LOG for _ in range(n)]
        
        # 实际使用中，这里需要运行一次 DFS 来计算 level 和 up[i][0] (直接父节点)
        # 然后通过动态规划填充 up 表:
        # for j in range(1, self.LOG):
        #     for i in range(self.n):
        #         if self.up[i][j-1] != -1:
        #             self.up[i][j] = self.up[self.up[i][j-1]][j-1]

    def get_lca(self, u, v):
        # 1. 确保 u 比 v 深 (如果不是，交换它们)
        if self.level[u] < self.level[v]:
            u, v = v, u
        
        # 2. 将 u 提升到与 v 同一高度
        for j in range(self.LOG - 1, -1, -1):
            if self.level[u] - (1 << j) >= self.level[v]:
                u = self.up[u][j]
        
        if u == v:
            return u
        
        # 3. 两人一起向上跳，直到 LCA 的正下方
        for j in range(self.LOG - 1, -1, -1):
            if self.up[u][j] != self.up[v][j]:
                u = self.up[u][j]
                v = self.up[v][j]
                
        return self.up[u][0]

小结

LCA 是调和的算法。无论是合并代码还是追溯血缘，它通过高效地在历史中回溯，帮我们找到了分歧发生的那个精确时刻。

Luke Sun