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

# 1676. Lowest Common Ancestor of a Binary Tree IV

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

這次不是給兩個節點，而是給**一組節點** `nodes`，要找它們全部的最近共同祖先。所有節點都保證存在於樹中。

## 思路

[236](/interview/coding/236-lowest-common-ancestor-of-a-binary-tree) 的骨架連改都不太需要改。回頭看那份程式碼裡唯一跟「兩個」有關的一行：

```python
if p == root or q == root:
    return root
```

它問的其實是「**我是不是目標之一**」。目標從兩個變成一堆，這句話一個字都不用改，只是判斷方式從兩次比較換成集合查找：

```python
if root in targets:
    return root
```

其他三種情況（左右各回報一個 → 我是答案；只有一邊 → 往上傳；都沒有 → `None`）**完全不用動**。

### 為什麼「左右各一個」對多節點依然成立

兩個節點的版本很直觀：分居兩側，我就是分岔點。多個節點時的推理也一樣 ——

如果左子樹回報了東西、右子樹也回報了東西，代表目標集合**跨越了我的左右兩側**。那麼任何比我更深的節點都只會落在其中一側，涵蓋不了全部，所以我就是最深的共同祖先。

而 `root in targets` 提早回傳一樣安全：既然我自己就是目標之一，我的子樹外面若還有其他目標，那答案會在更上層由「左右各一個」那條規則接手；若其他目標都在我的子樹裡，那我本來就是答案。

**這也解釋了為什麼 [1650](/interview/coding/1650-lowest-common-ancestor-of-a-binary-tree-iii) 的第一個解法早就寫成 `root in nodes`** —— 那個形式本來就是通用的，兩個節點只是集合大小為 2 的特例。

## 解題方向

```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', nodes: 'List[TreeNode]') -> 'TreeNode':
        targets = set(nodes)

        def helper(node):
            if not node:
                return None
            if node in targets:
                return node

            left = helper(node.left)
            right = helper(node.right)

            if left and right:
                return node
            return left or right

        return helper(root)
```

先把 `nodes` 轉成 `set`，查找才是 $O(1)$；直接對 list 用 `in` 會讓每個節點都做一次線性掃描，整體變成 $O(n \times k)$。

節點是用物件同一性比較的，`set` 用的是預設的 `hash`，所以不需要節點的值唯一 —— 這點跟 236 一樣。

## 補充

**整個 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. LCA III](/interview/coding/1650-lowest-common-ancestor-of-a-binary-tree-iii) | 有 **parent** 指標，拿不到 root | 由下往上，兩條鏈求相交 |
| 1676 | 給的是**一組節點** | **`root in nodes`** 取代兩個比較 |

**如果再把 1644 的條件疊上來**（一組節點、而且可能有人不在樹裡），做法就是把兩題合起來：`root in targets` 之後不提早回傳，走完整棵樹再檢查有幾個目標真的出現過。這一題沒有要求，但那是這個家族的完整形。

## 複雜度

- 時間 $O(n)$ — 每個節點最多走一次，`set` 查找是 $O(1)$
- 空間 $O(k + h)$ — `targets` 佔 $O(k)$，遞迴堆疊佔 $O(h)$

其中 $n$ 是節點數、$k$ 是 `nodes` 的長度、`h` 是樹高。