---
title: "1650. Lowest Common Ancestor of a Binary Tree III"
url: "https://laigary.com/interview/coding/1650-lowest-common-ancestor-of-a-binary-tree-iii"
type: "note"
section: "coding"
date: "2023-01-31"
updated: "2026-07-28"
tags: ["Linked List", "Tree", "Hash Table"]
---

# 1650. Lowest Common Ancestor of a Binary Tree III

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

一樣找最近共同祖先，但這題**沒有給 root**，只給了 `p` 和 `q` 兩個節點 —— 而每個節點多了一個 `parent` 指標。

## 思路

`parent` 指標把問題整個翻過來了。原本只能由上往下找，現在**可以由下往上走**。

而「從 `p` 一路往上到 root」就是一條鏈結串列，`q` 也是。這兩條鏈的終點都是 root，所以它們一定會在某個點合併 —— **第一個合併的點就是 LCA**。

問題於是變成：兩條共用尾巴的鏈結串列，求它們的第一個交會點。

### 做法一：先爬回 root，再用 236 的解法

最直接的想法是把缺的 root 補回來 —— 從 `p` 一路往上就找得到。拿到 root 之後，這題就變回 [236](/interview/coding/236-lowest-common-ancestor-of-a-binary-tree)。

這個做法能過，但**完全沒用到 `parent` 指標的價值**：爬上去只花 $O(h)$，卻又用 $O(n)$ 把整棵樹遍歷一次。

### 做法二：一邊往上爬一邊記路徑

直接在往上爬的過程中就把答案找出來：

1. 從 `p` 往上走到 root，把路徑上經過的節點全部記進一個 set。**LCA 一定在這條路徑上**（因為 LCA 是 `p` 的祖先）
2. 從 `q` 往上走，遇到的第一個「已經在 set 裡」的節點，就是 LCA

第 1 步爬的時候如果直接撞到 `q`，那代表 `q` 是 `p` 的祖先，`q` 自己就是答案。

## 解題方向

### 一、爬回 root 再套用 236

```python
class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        t = p
        while t.parent:
            t = t.parent
        root = t
        nodes = set([p, q])
        def helper(root, nodes):
            if not root:
                return None
            if root in nodes:
                return root
            left = helper(root.left, nodes)
            right = helper(root.right, nodes)
            if left and right:
                return root
            return left or right
        return helper(root, nodes)
```

這裡順手把 236 的 `p == root or q == root` 寫成了 `root in nodes` —— 這個寫法直接就是 [1676](/interview/coding/1676-lowest-common-ancestor-of-a-binary-tree-iv) 需要的形式。

### 二、只靠 parent 往上走

```python
class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        # 由 p 開始向上搜尋 root 節點，並且把路徑上造訪過的節點都記錄起來
        # 因為最近共同祖先一定會在這個 set 裡面。
        # 如果在向上找的過程中，就遇到了 q 節點，那 q 就是最近共同祖先。
        t = p
        visited = {t}
        while t.parent:
            t = t.parent
            visited.add(t)
            if t == q:
                return q
        root = t
        k = q
        # 由 q 開始向上搜尋，如果找到有節點已經造訪過，那那個節點就是最近共同祖先
        while k.parent:
            k = k.parent
            if k in visited:
                return k
        # 這一行其實用不到，因為 root 其實一定會在造訪過的節點了。
        return root
```

這版只走了兩條「往上」的路徑，跟樹的大小無關 —— 時間從 $O(n)$ 降到 $O(h)$。

**兩版對 `p` 就是 `q` 的行為不一樣。** 第一版的 `nodes = {p, q}` 會塌成一個元素，`root in nodes` 一撞到就回傳 `p`，正確。第二版則是從 `q.parent` 開始往上找，永遠不會檢查 `q` 自己，所以會回傳 `p.parent`：

```text
p 就是 q 時：  版本一 → p  ✅      版本二 → p.parent  ❌
```

題目保證 `p != q`，所以實際上不會踩到。但如果要讓第二版也穩，把第二個迴圈改成先檢查 `k` 再往上（或一開始就 `if p == q: return p`）就行了。

## 補充

**這題其實是鏈結串列題。** 「兩條共用尾巴的鏈求交會點」有一個不用額外空間的經典解法：先各自算出長度，讓長的那條先走差值步，然後兩邊齊步走，相遇處就是交點。空間可以做到 $O(1)$。我這裡寫的是 set 版，比較直觀。

**整個 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. LCA II](/interview/coding/1644-lowest-common-ancestor-of-a-binary-tree-ii) | `p`、`q` **可能不存在** | 不能提早回傳，要走完整棵樹 |
| 1650 | 有 **parent** 指標，拿不到 root | **由下往上，兩條鏈求相交** |
| [1676. LCA IV](/interview/coding/1676-lowest-common-ancestor-of-a-binary-tree-iv) | 給的是**一組節點** | `root in nodes` 取代兩個比較 |

## 複雜度

**做法一（爬回 root + 遍歷）**
- 時間 $O(n)$ — 遍歷整棵樹
- 空間 $O(h)$ — 遞迴堆疊

**做法二（只往上走）**
- 時間 $O(h)$ — 兩條往上的路徑，各最多走樹高那麼多步
- 空間 $O(h)$ — `visited` 裝的是 `p` 到 root 的路徑

其中 $n$ 是節點數、`h` 是樹高。做法二快在它從來沒有碰過 `p`、`q` 祖先鏈以外的任何節點。