演算法面試：如何找出二元樹的最低共同祖先？

題目與適用情境

給定一棵任意二元樹和其中兩個不同節點 p、q。一個節點也算自己的祖先；兩者的最低共同祖先 是同時包含 p、q 的最深節點。例如，若 p 本身是 q 的祖先，答案就是 p。

這道題的契約有四個關鍵點：樹不是二元搜尋樹；輸入給的是節點參照而不是節點值；不同節點可以有 相同值；基礎版本保證 p 和 q 都在樹中。實作若偷偷依數值比較，或在存在性沒有保證時仍套用 基礎遞迴，都會在追問中出錯。

a
      /   \
     b     c
    / \   / \
   d   e f   g
        \
         h

在這棵樹中，LCA(d, h) = b，LCA(b, h) = b，LCA(e, f) = a。目標職位是需要掌握樹走訪、 遞迴語意與複雜度分析的軟體工程師。基礎問題只做一次查詢；深度失控、目標可能缺少、節點帶父指標 或同一棵樹有大量查詢，都屬於會改變解法的後續約束。

面試官評估重點

面試官首先會看候選人是否把「最低」翻譯成可執行結構：從根到 p、q 的兩條路徑，最後一個 共同節點就是答案。這個路徑方案正確，但沒有必要明確保存兩條路徑。更好的推導是讓每棵子樹回報： 「這裡沒有目標」「這裡找到一個目標」或「這裡已經找到兩個目標的交會點」。

好的回答會替遞迴回傳值給出精確定義。在以 node 為根的子樹裡，函式回傳：

• null：子樹不包含 p 或 q；
• p 或 q：子樹目前只需要把一個已找到的目標向上傳遞；
• 其他節點：該節點已經是這棵子樹內的最低共同祖先。

左右遞迴結果都非空時，兩個目標從目前節點的不同方向交會，目前節點就是答案。只有一側非空時， 那一側的結果繼續向上傳遞。目前節點等於目標時立即回傳，是因為基礎契約保證另一個目標存在： 另一個目標若在其子樹內，目前節點就是祖先；若在外部，目前節點也需要向上回報已找到一個目標。

還要能指出契約陷阱。基礎演算法在 q 不存在時可能回傳 p，所以它沒有順便驗證兩個目標都存在。 把存在性保證刪掉後，回傳值必須同時攜帶配對數量。對於高度為 h、節點數為 n 的樹，單次 查詢最壞會造訪每個節點一次，時間為 O(n)，遞迴堆疊為 O(h)；傾斜樹中 h = n，呼叫堆疊 本身就可能成為故障點。

回答前需要釐清的問題

• 輸入是節點參照還是節點值？ 節點參照允許值重複，比較應使用 node === p。只有值唯一且

契約明確時，才可以依值定位。

• 兩個目標是否保證存在且互不相同？ 基礎遞迴依賴存在性保證。任一目標可能缺少時，要回傳

配對數量；若允許 p === q，還要明確找到一次是否足夠。

• 這是普通二元樹還是二元搜尋樹？ 普通樹必須搜尋結構；BST 可以依鍵的相對大小沿一條路徑

下降，但重複鍵和參照語意會讓這個捷徑失效。

• 樹的最大節點數與高度是多少？ 平衡樹的遞迴深度為 O(log n)；十萬個節點的鏈狀樹應考慮

顯式堆疊與父映射，避免語言執行環境堆疊溢位。

• 同一棵靜態樹要回答多少次查詢？ 一次查詢直接 DFS 最簡單。大量查詢可先計算深度和

2^k 級祖先，再把單次查詢降為 O(log n)。

• 節點是否已經有 parent 指標？ 有父指標時不必從根走訪整棵樹，可以對齊深度後同時向上，

或記錄一條祖先鏈再找交點。

30 秒回答框架

「我會先確認這是普通二元樹，p、q 是節點參照且都保證存在，所以值重複不影響判斷。我讓遞迴 函式回傳目前子樹發現的目標，或已經形成的共同祖先。空節點回傳 null，目前節點是 p 或 q 時回傳自己；遞迴左右子樹後，如果兩邊都非空，表示兩個目標在目前節點交會，回傳目前節點，否則 回傳唯一非空的一邊。每個節點最多造訪一次，最壞時間 O(n)，遞迴堆疊 O(h)。我會用目標互為 祖先、分處兩側、值重複和傾斜樹測試。若目標可能缺少，回傳值要增加配對數；若高度不受控，就改用 顯式堆疊建立父映射。」

分步深入解答

第一步：從明確路徑得到正確基線

最直觀的方法是分別找出根到 p 和根到 q 的路徑，再從頭比較，最後一個相同節點就是最低共同 祖先。它很適合先說明定義，也容易驗證目標是否存在。兩次 DFS 仍是 O(n) 時間，路徑與遞迴堆疊 占 O(h)；若實作把搜尋過的全部節點都保留，空間可能擴大到 O(n)。

路徑法的冗餘在於兩次搜尋共享大量前綴。我們真正需要的只有「一棵子樹向父節點回報了什麼」， 因此可以把兩條路徑壓縮為一次後序走訪。

第二步：定義回傳值並寫出一次走訪

interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (root === null || root === p || root === q) {
    return root
  }

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left !== null && right !== null) {
    return root
  }

  return left ?? right
}

這段程式碼比較物件身分，不讀取 value，所以兩個節點同值也不會混淆。後序順序很關鍵：目前 節點需要先知道左右子樹各自是否回傳目標或已經找到的答案，才能判斷自己是否是首次交會點。

第三步：用不變量證明，不靠範例猜測

對任意以 node 為根的子樹，假設兩個遞迴呼叫都滿足回傳值定義。

1. node 為空時，子樹沒有目標，回傳 null 正確。
2. node 等於 p 或 q 時，回傳 node。因為兩個目標保證存在，目前目標若包含另一個目標，

自己就是最低共同祖先；否則它需要繼續向祖先回報已找到一個目標。

1. 左右結果都非空時，兩個目標分別由兩側回報。任何更深節點都只屬於一側，無法同時包含兩者，

所以 node 是最深的共同祖先。

1. 只有一側非空時，目前節點尚未形成新的交會點；那一側回傳的目標或答案仍是應該向上傳遞的

唯一有效結果。兩側都空則回傳 null。

由結構歸納，根節點的回傳值就是整棵樹的最低共同祖先。這個證明也涵蓋「p 是 q 的祖先」 這個容易漏掉的情況：走訪到 p 時直接回傳 p，不需要繼續從其子樹把 q 再回傳一次。

第四步：分析真實的時間與空間

最壞情況下，函式造訪 n 個節點，每個節點只做常數工作，時間為 O(n)。提早遇到目標可能少 造訪部分子樹，但不能把最佳情況寫成最壞複雜度。

輔助空間由遞迴深度決定，為 O(h)。平衡樹中 h = O(log n)；完全傾斜時 h = n。輸出只 是一個節點參照，不計入輔助空間。宣稱「空間 O(1)」會忽略呼叫堆疊。

第五步：目標可能缺少時改變回傳契約

若 API 不保證目標存在，基礎函式會誤報：樹中只有 p 時，它會把 p 一路傳到根並回傳。安全 版本必須區分「候選節點」與「實際找到幾個目標」。

interface SearchResult {
  candidate: TreeNode | null
  matches: number
}

function lowestCommonAncestorValidated(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  function visit(node: TreeNode | null): SearchResult {
    if (node === null) {
      return { candidate: null, matches: 0 }
    }

    const left = visit(node.left)
    if (left.matches === 2) {
      return left
    }

    const right = visit(node.right)
    if (right.matches === 2) {
      return right
    }

    const self = node === p || node === q ? 1 : 0
    const matches = left.matches + right.matches + self

    return {
      candidate: matches === 2 ? node : left.candidate ?? right.candidate ?? (self ? node : null),
      matches,
    }
  }

  const result = visit(root)
  return result.matches === 2 ? result.candidate : null
}

這裡仍假設 p !== q。若允許同一參照作為兩個目標，就應先另外約定：找到該節點一次即回傳它， 而不能繼續要求 matches === 2。約束變化必須先於程式碼變化。

第六步：深樹使用顯式堆疊與父映射

當高度可能接近十萬，遞迴的漸進空間沒有改變，但執行環境呼叫堆疊可能先溢位。可以用顯式堆疊 走訪，記錄 parent.get(child) = node，直到 p、q 都出現在映射中。接著把 p 到根的祖先 放入集合，從 q 向上遇到的第一個集合成員就是答案。

該方案時間仍為 O(n)，顯式空間為 O(n)。它比遞迴占更多堆積記憶體，卻把資源從大小受限的 呼叫堆疊移到可控資料結構。對高度有合理上限的一次查詢，遞迴版更短、更容易證明，不必為了極端 約束預設採用父映射。

第七步：用對抗用例驗證語意

至少涵蓋以下用例：

除了固定範例，也可以產生隨機小樹，用路徑基線與一次走訪結果依節點參照比較。基線和最佳化方案 來自不同實作思路，比只寫幾個手動斷言更能有效發現錯誤。

高品質示範回答

「我先固定契約：這是普通二元樹，p 和 q 是不同節點的參照、都保證存在，節點值可能重複， 所以程式碼比較參照而不比較值。

我會做一次後序 DFS。函式對一棵子樹回傳 null、其中一個目標，或已經找到的最低共同祖先。 空節點回傳 null，目前節點等於任一目標時回傳自己。左右遞迴後，兩邊都非空表示兩個目標在目前 節點首次交會，所以回傳目前節點；只有一邊非空就把那邊向上傳遞。

正確性來自這個回傳值不變量。若兩個目標分處左右子樹，任何更深節點都不可能同時包含它們；若 一個目標是另一個的祖先，走訪到祖先目標時直接回傳它也正好符合定義。最壞造訪每個節點一次， 時間 O(n)，遞迴堆疊 O(h)，傾斜樹時會退化為 O(n) 堆疊深度。

我會測試分處兩側、互為祖先、同一深子樹和重複值。若目標不保證存在，目前函式可能把唯一存在的 目標當答案，我會讓遞迴額外回傳配對數，只有找到兩個目標才接受候選節點。若樹可能非常深，就用 顯式堆疊建立父映射，避免呼叫堆疊溢位。」

常見錯誤

• 把二元樹當 BST 依值選左右 → 普通二元樹沒有排序性，重複值也無法表示節點身分 →

依結構搜尋並比較節點參照。

• 左右結果任一非空就回傳目前節點 → 單側只有一個目標時會把答案抬到根 → **只有兩側都非空

才回傳目前節點，否則傳遞非空結果。**

• 認為 p 必須嚴格位於答案下方 → 一個節點也算自己的祖先，p 可能就是答案 → **把目前

節點等於目標作為遞迴基例。**

• 在缺少節點契約下重用基礎演算法 → 只找到一個目標也會回傳非空結果 → **同時回傳配對數量，

找到兩個目標才成功。**

• 宣稱輔助空間 O(1) → 遞迴呼叫堆疊隨樹高增長，傾斜樹為 O(n) → **依 O(h) 回報，並

在深度不受控時改用顯式堆疊。**

• 為一次查詢先做二進位提升 → 預處理程式碼與 O(n log n) 空間沒有被查詢量攤平 → **單次

查詢使用一次 DFS，大量查詢再預處理。**

• 只測試兩個葉節點分處兩側 → 無法暴露祖先目標、重複值、缺少節點和深度問題 → **用契約

邊界組織測試矩陣。**

追問與應對

如果 p 或 q 可能不在樹中，如何確保不誤報？

讓遞迴結果包含候選節點與配對數。基礎問題中兩個目標不同，因此總配對數只有 0、1、2。 根結果為 2 才回傳候選 LCA，否則回傳 null。不能先執行基礎演算法再檢查回傳值是否非空，因為 唯一存在的目標本身就是非空回傳值。

如果樹有十萬個節點且可能完全傾斜呢？

改用顯式堆疊建立父映射。找到兩個目標後，把 p 的祖先放入集合，再沿 q 的父鏈找第一個交點。 時間 O(n)、堆積空間 O(n)，但不會消耗十萬層語言呼叫堆疊。若記憶體約束也很緊，應進一步 確認樹是否能提供 parent 指標或受控的走訪介面，而不是假設遞迴可用。

如果同一棵靜態樹要回答一百萬次 LCA 查詢呢？

每次 O(n) DFS 不再合適。先 DFS 計算深度和每個節點的 2^k 級祖先，預處理時間與空間均為 O(n log n)。查詢時先把較深節點提升到同一深度，再從最大的 k 向下同時提升兩個節點，單次 為 O(log n)。若查詢量更大且實作複雜度可接受，還可評估 Euler tour 加 RMQ；選擇取決於更新 頻率、記憶體和查詢延遲目標。

如果節點已經有 parent 指標，仍需要從根走訪嗎？

不需要。可以先計算兩節點深度，把較深者上移到同一層，再同步向上直到相等，時間為 O(h)、 額外空間 O(1)。也可以記錄 p 的全部祖先，再沿 q 上移找第一個交點，程式碼更直接但需要 O(h) 集合空間。

如果輸入是二元搜尋樹，可以如何簡化？

在鍵唯一且依鍵尋找目標的契約下，若 p、q 都小於目前鍵就向左，都大於就向右，否則目前 節點就是分叉點或其中一個目標，時間 O(h)、迭代空間 O(1)。若節點值可重複或輸入仍以參照 標識目標，必須先定義重複鍵放置規則與定位方式；不能只憑兩個數值安全地取代普通樹演算法。