最近公共祖先 (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