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

# 235. Lowest Common Ancestor of a Binary Search Tree

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

跟 [236](/interview/coding/236-lowest-common-ancestor-of-a-binary-tree) 一樣要找最近共同祖先，差別只有一個：**這棵樹是 BST**。

## 思路

[236](/interview/coding/236-lowest-common-ancestor-of-a-binary-tree) 那份通用的後序解法直接拿來用就會過 —— 做法完全一模一樣，BST 的性質一點都沒用到。但那樣就浪費了這題的條件。

BST 的性質是「左子樹的值全部小於自己，右子樹全部大於自己」。這代表**站在任何一個節點上，都可以只靠比較值就知道 `p`、`q` 在哪一邊**，根本不需要去遍歷子樹。

站在 `node` 上有三種情況：

- `p.val` 和 `q.val` **都小於** `node.val` → 兩個都在左子樹，往左走
- `p.val` 和 `q.val` **都大於** `node.val` → 兩個都在右子樹，往右走
- 其餘（一大一小，或其中一個剛好等於 `node.val`）→ **`node` 就是答案**

第三種情況為什麼是答案？因為它正是 `p` 和 `q` **第一次分道揚鑣**的地方。再往下走任何一步，就只會落在其中一個的那一側，另一個就被丟掉了 —— 所以這裡就是最深的共同祖先。

「一個剛好等於 `node`」也涵蓋在第三種：那代表其中一個是另一個的祖先，答案就是它自己。

**所以這題只需要往下走一條路徑，不需要遍歷整棵樹。**

## 解題方向

### BST 專屬：沿著值域往下走

```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':
        node = root
        while node:
            if p.val < node.val and q.val < node.val:
                node = node.left
            elif p.val > node.val and q.val > node.val:
                node = node.right
            else:
                return node
        return None
```

寫成迴圈而不是遞迴，空間就是 $O(1)$ —— 因為這題只往下走一條路，沒有「回頭處理另一邊」的需求，不需要堆疊。

這也是 BST 題的通則：**只要每一步都能靠比較決定往哪一邊走，就不需要遞迴**，跟 [二分搜尋](/interview/coding/binary-search-template) 是同一個形狀。

### 通用解法（也會過）

[236](/interview/coding/236-lowest-common-ancestor-of-a-binary-tree) 的後序版對 BST 一樣正確，只是慢一些：

```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
```

兩份的差別是 $O(h)$ 對 $O(n)$ —— 通用版會把整棵樹走過一遍才知道答案，BST 版走一條路就結束。

## 補充

**整個 LCA 家族**：

| 題目 | 條件的差異 | 解法的差異 |
|---|---|---|
| [236. LCA of a Binary Tree](/interview/coding/236-lowest-common-ancestor-of-a-binary-tree) | 一般二元樹，`p`、`q` 保證存在 | 後序回報（原型） |
| 235 | 是 **BST** | 用值域直接往下走 |
| [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` 取代兩個比較 |

**其他「靠值域往下走」的 BST 題**：[270. Closest BST Value](/interview/coding/270-closest-binary-search-tree-value)、[700. Search in a BST](/interview/coding/700-search-in-a-binary-search-tree)、[701. Insert into a BST](/interview/coding/701-insert-into-a-binary-search-tree)、[98. Validate BST](/interview/coding/98-validate-binary-search-tree)。

## 複雜度

**BST 版**
- 時間 $O(h)$ — 只走一條從根往下的路徑
- 空間 $O(1)$ — 迭代，只有一個 `node` 變數

**通用版**
- 時間 $O(n)$ — 要遍歷整棵樹
- 空間 $O(h)$ — 遞迴堆疊

其中 $n$ 是節點數、`h` 是樹高。平衡的 BST 是 $O(\log n)$，退化成一條鏈時是 $O(n)$。