1644. Lowest Common Ancestor of a Binary Tree II

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

跟 236 一樣找最近共同祖先，但不保證 p 和 q 在樹裡。只要有一個不在，就回傳 None。

這個系列只有這一題要小心一點，因為做法雖然一樣，卻有一個前提被抽掉了。

思路

236 的程式碼有一行是靠「保證存在」才成立的：

if p == root or q == root:
    return root          # 直接回傳，不往下確認另一個在不在

在 236 裡這樣做沒問題 —— 既然 q 保證存在，而我們已經站在 p 上，q 就只可能在 p 的子樹裡。但這題的 q 可能根本不存在，那 p 就不該是答案。

所以必須改兩件事：

不能提早回傳。 遇到 p 或 q 時要先把左右子樹都走完，再決定回傳什麼 —— 也就是把那個判斷從遞迴之前搬到遞迴之後
要另外確認兩個都真的出現過。 走訪的過程中把碰到的節點都記下來，最後檢查 p 和 q 是不是都在裡面

第 2 點是這題真正的代價：236 可以找到答案就停，這題一定要走完整棵樹，因為「不存在」這件事只有走完才能確定。

解題方向

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        visited = set()
        nodes = set()
        nodes.add(p)
        nodes.add(q)
        def helper(root, nodes):
            visited.add(root)
            if not root:
                return None
            left = helper(root.left, nodes)
            right = helper(root.right, nodes)
            if root in nodes:
                return root
            if left and right:
                return root
            return left or right
        res = helper(root, nodes)
        if q not in visited or p not in visited:
            return None
        else:
            return res

注意 if root in nodes: return root 的位置 —— 它在兩行遞迴下面。這一行的位置就是 236 和這題的全部差異：

236：  檢查自己 → 遞迴左右        （找到就停，不再往下）
1644： 遞迴左右 → 檢查自己        （一定走完，才能確認存在性）

visited 收集的是「真的走訪過的節點」，所以最後 p not in visited or q not in visited 就能判斷有沒有人缺席。

順帶一提 visited.add(root) 寫在 if not root 之前，所以 None 也會被放進 visited。這不影響正確性（p、q 都是實際節點），但把兩行對調會更乾淨。

補充

整個 LCA 家族：

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

也可以不用 visited：讓遞迴額外回傳「找到幾個目標」，最後檢查是不是 2。效果一樣，差別只在存性資訊放在 set 裡還是回傳值裡。我寫的是 set 版，因為它跟 236 的骨架差最少。

複雜度

時間 $O (n)$ — 一定會走遍每個節點（這是跟 236 的實質差異：236 最壞才是 $O (n)$ ，這題一律是）
空間 $O (n)$ — visited 最多裝下所有節點，加上 $O (h)$ 的遞迴堆疊

其中 $n$ 是節點數、h 是樹高。