Lowest Common Ancestor of a Binary Tree
題目描述
給定一棵二元樹的根節點 root 和兩個節點 p、q，回傳 p 和 q 的最低公共祖先（LCA）。LCA 定義為：在樹中同時是 p 和 q 祖先的最深節點。
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 5 是 4 的祖先，且 5 也是自己的祖先
解題思路
Base Case
node 為 null 回傳 null；node 等於 p 或 q 時直接回傳 node 本身
遞迴左子樹
left = LCA(root.left, p, q) 在左子樹中搜尋 p 或 q
遞迴右子樹
right = LCA(root.right, p, q) 在右子樹中搜尋 p 或 q
判斷結果
left 和 right 都非 null 代表 p、q 分居兩側，當前節點就是 LCA；只有一邊非 null 則往上傳遞
程式碼
C#
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Base case: null 或找到 p/q
if (root == null || root == p || root == q) return root;
var left = LowestCommonAncestor(root.left, p, q);
var right = LowestCommonAncestor(root.right, p, q);
// 左右都找到 → 當前節點就是 LCA
if (left != null && right != null) return root;
// 只有一邊找到 → 往上傳
return left ?? right;
}
}TypeScript
function lowestCommonAncestor(
root: TreeNode | null, p: TreeNode, q: TreeNode
): TreeNode | null {
if (!root || root === p || root === q) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root; // 左右都找到
return left ?? right; // 只有一邊
}Python
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right: # 左右都找到
return root
return left or right # 只有一邊複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(h) |
Time O(n) 是因為最壞情況需要遍歷所有節點才能找到 p 和 q。Space O(h) 是遞迴 call stack 深度，平衡樹 O(log n)，偏斜樹 O(n)。
邊界情況
- p 是 q 的祖先：如 p=5, q=4 且 4 在 5 的子樹中，遞迴到 5 時直接回傳 5（LCA 就是 p 本身）
- p 和 q 是同一個節點：base case 直接回傳該節點
- p 和 q 分別在根的左右兩側：左右子樹各回傳一個非 null，根節點就是 LCA
圖解
圖表展示了 p=5, q=1 的查找過程：左子樹找到 p=5 回傳非 null，右子樹找到 q=1 回傳非 null，兩邊都非 null 代表 p 和 q 分居兩側，根節點 3 就是 LCA。
進階觀點
💡面試追問
Q: 如果 p 或 q 不在樹中怎麼辦？ A: 當前解法假設 p 和 q 都存在。若不確定，需要加兩個 boolean flag（foundP、foundQ）在遍歷完整棵樹後確認兩者都被找到。如果只找到一個，回傳 null 而非錯誤的 LCA。
Q: BST 版本（LC 235）如何利用 BST 性質？ A: 如果 p.val 和 q.val 都小於 root.val，LCA 一定在左子樹；都大於 root.val 則在右子樹。當 p 和 q 的值分岔（一個小於 root 一個大於 root），root 就是 LCA。Time O(h)，不需遍歷所有節點。
變體題：LC 1644 LCA II（節點可能不存在）、LC 1676 LCA IV（多個節點的 LCA）。
理解測驗
🤔 為什麼遇到 p 或 q 就直接回傳，不繼續往下找？
🤔 左子樹回傳 null、右子樹回傳非 null，這代表什麼？