1676. Lowest Common Ancestor of a Binary Tree IV

──────────────────────────────────────────────────────────────────────

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

思路

236 的骨架連改都不太需要改。回頭看那份程式碼裡唯一跟「兩個」有關的一行：

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

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

if root in targets:
    return root

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

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

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

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

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

這也解釋了為什麼 1650 的第一個解法早就寫成 root in nodes —— 那個形式本來就是通用的，兩個節點只是集合大小為 2 的特例。

解題方向

# 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	一般二元樹，`p`、`q` 保證存在	後序回報（原型）
235. LCA of a BST	是 BST	用值域直接往下走
1644. LCA II	`p`、`q` 可能不存在	不能提早回傳，要走完整棵樹
1650. LCA 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 是樹高。