題目與適用情境
給定一棵任意二元樹和其中兩個不同節點 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 為根的子樹，假設兩個遞迴呼叫都滿足回傳值定義。
node為空時，子樹沒有目標，回傳null正確。node等於p或q時，回傳node。因為兩個目標保證存在，目前目標若包含另一個目標，
自己就是最低共同祖先；否則它需要繼續向祖先回報已找到一個目標。
- 左右結果都非空時，兩個目標分別由兩側回報。任何更深節點都只屬於一側，無法同時包含兩者，
所以 node 是最深的共同祖先。
- 只有一側非空時，目前節點尚未形成新的交會點；那一側回傳的目標或答案仍是應該向上傳遞的
唯一有效結果。兩側都空則回傳 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 分處根的兩側 | 回傳根 | 只搜尋一條路徑 | | p 是 q 的祖先 | 回傳 p | 忘記節點也是自己的祖先 | | 兩節點位於同一深子樹 | 回傳子樹內節點 | 回傳了過高的共同祖先 | | 兩個不同節點的 value 相同 | 依參照回傳正確節點 | 錯把值當身分 | | 單節點樹且 p === q 的擴充契約 | 回傳該節點 | 沒有定義相同目標 | | 一個目標缺少 | 安全版本回傳 null | 基礎版誤報 | | 十萬個節點的鏈 | 迭代版完成 | 遞迴堆疊溢位 |
除了固定範例，也可以產生隨機小樹，用路徑基線與一次走訪結果依節點參照比較。基線和最佳化方案 來自不同實作思路，比只寫幾個手動斷言更能有效發現錯誤。
高品質示範回答
「我先固定契約：這是普通二元樹，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)。若節點值可重複或輸入仍以參照 標識目標，必須先定義重複鍵放置規則與定位方式；不能只憑兩個數值安全地取代普通樹演算法。