---
title: "1644. Lowest Common Ancestor of a Binary Tree II"
url: "https://laigary.com/interview/coding/1644-lowest-common-ancestor-of-a-binary-tree-ii"
type: "note"
section: "coding"
date: "2023-01-31"
updated: "2026-07-28"
tags: ["Tree", "Depth-First Search"]
---

# 1644. Lowest Common Ancestor of a Binary Tree II

[1644\. Lowest Common Ancestor of a Binary Tree II](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/)

跟 [236](/interview/coding/236-lowest-common-ancestor-of-a-binary-tree) 一樣找最近共同祖先，但**不保證 `p` 和 `q` 在樹裡**。只要有一個不在，就回傳 `None`。

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

## 思路

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

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

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

所以必須改兩件事：

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

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

## 解題方向

```python
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 和這題的全部差異：

```text
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](/interview/coding/236-lowest-common-ancestor-of-a-binary-tree) | 一般二元樹，`p`、`q` 保證存在 | 後序回報（原型） |
| [235. LCA of a BST](/interview/coding/235-lowest-common-ancestor-of-a-binary-search-tree) | 是 **BST** | 用值域直接往下走 |
| 1644 | `p`、`q` **可能不存在** | **不能提早回傳**，要走完整棵樹確認 |
| [1650. LCA III](/interview/coding/1650-lowest-common-ancestor-of-a-binary-tree-iii) | 有 **parent** 指標，拿不到 root | 退化成兩條鏈結串列求相交 |
| [1676. LCA IV](/interview/coding/1676-lowest-common-ancestor-of-a-binary-tree-iv) | 給的是**一組節點** | `root in nodes` 取代兩個比較 |

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

## 複雜度

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

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