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

# 236. Lowest Common Ancestor of a Binary Tree

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

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

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

## 思路

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

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

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

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

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

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

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

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

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

這個前提在 [1644](/interview/coding/1644-lowest-common-ancestor-of-a-binary-tree-ii) 被拿掉了（`p`、`q` 可能根本不在樹裡），所以那題就不能提早回傳，必須走完整棵樹。**這是整個家族裡最重要的一個分界。**

## 解題方向

```python
# 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](/interview/coding/235-lowest-common-ancestor-of-a-binary-search-tree) | 是 **BST** | 可以用值域直接往下走，$O(h)$ 時間、$O(1)$ 空間 |
| [1644. LCA II](/interview/coding/1644-lowest-common-ancestor-of-a-binary-tree-ii) | `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` 取代 `root == p or root == q` |

**同樣是「後序回傳一個值」的樹形遞迴**：[124. Binary Tree Maximum Path Sum](/interview/coding/124-binary-tree-maximum-path-sum)、[543. Diameter of Binary Tree](/interview/coding/543-diameter-of-binary-tree)、[250. Count Univalue Subtrees](/interview/coding/250-count-univalue-subtrees)。共同點都是「先問清楚回傳值代表什麼」，程式碼才寫得下去。

## 複雜度

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

其中 $n$ 是節點數。