236. Lowest Common Ancestor of a Binary Tree

──────────────────────────────────────────────────────────────────────

給一棵二元樹和其中兩個節點 p、q，找出它們最近的共同祖先。題目保證兩個節點都存在於樹中。

這題是整個 LCA 家族的原型，其他四題都是在它上面改條件。

思路

LCA 的定義是「同時是 p 和 q 的祖先，而且最深的那一個」。從上往下找很難判斷誰最深，但從下往上回報就很自然 —— 這是後序遍歷的形狀。

關鍵是先把遞迴的回傳值定義清楚：

lowestCommonAncestor(node, p, q) 回傳「node 的子樹裡，找到的最有用的那個節點」 —— 如果 p 和 q 都在這棵子樹裡，回傳它們的 LCA；如果只找到其中一個，就回傳那一個；都沒找到回傳 None。

把回傳值的意義用一句話講死，是所有樹形遞迴的第一步（見 Tree 遍歷模板）。定義好之後，四種情況就自己冒出來了：

情況	回傳
`root` 本身就是 `p` 或 `q`	`root`
左右子樹各回報了一個	`root` —— p、q 分居兩側，我就是答案
只有一邊有回報	把那一邊的結果往上傳
兩邊都沒有	`None`

第二種情況就是整題的核心：左右各找到一個，那分岔點就是我。

「自己就是 p 或 q 就直接回傳」為什麼安全

這是唯一需要停下來想的地方。假設 p 是 q 的祖先，走到 p 時我們直接回傳了 p，沒有繼續往下確認 q 在不在。這樣對嗎？

對，但前提是題目保證了 p 和 q 都存在於樹中。既然 q 一定存在，而我們又已經站在 p 上，那 q 只可能在 p 的子樹裡 —— 所以 p 就是 LCA，不需要驗證。

這個前提在 1644 被拿掉了（p、q 可能根本不在樹裡），所以那題就不能提早回傳，必須走完整棵樹。這是整個家族裡最重要的一個分界。

解題方向

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        if p == root or q == root:
            return root

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

        if left and right:
            return root
        if not left and not right:
            return None
        return left or right

return left or right 把「只有一邊有」和「哪一邊」兩件事合成一行 —— or 會回傳第一個為真的值，兩邊都是 None 時回傳 None。所以中間那個 if not left and not right: return None 其實可以省掉，寫出來只是讓四種情況一一對應，讀起來比較清楚。

比較是用 ==（也就是物件同一性），不是比 val。題目給的 p、q 是節點參考，樹裡也可能有重複的值，所以不能改成比值。

補充

整個 LCA 家族：五題的骨架都是上面這一份，差別只在題目改了什麼條件。

題目	條件的差異	解法的差異
236	一般二元樹，`p`、`q` 保證存在	後序回報（原型）
235. LCA of a BST	是 BST	可以用值域直接往下走， $O (h)$ 時間、 $O (1)$ 空間
1644. LCA II	`p`、`q` 可能不存在	不能提早回傳，要走完整棵樹確認
1650. LCA III	有 parent 指標，但拿不到 root	退化成兩條鏈結串列求相交
1676. LCA IV	給的是一組節點而非兩個	`root in nodes` 取代 `root == p or root == q`

同樣是「後序回傳一個值」的樹形遞迴：124. Binary Tree Maximum Path Sum、543. Diameter of Binary Tree、250. Count Univalue Subtrees。共同點都是「先問清楚回傳值代表什麼」，程式碼才寫得下去。

複雜度

時間 $O (n)$ — 最壞要走遍每個節點
空間 $O (h)$ — 遞迴堆疊，h 是樹高；平衡樹是 $O (\log n)$ ，斜樹退化成 $O (n)$

其中 $n$ 是節點數。