1650. Lowest Common Ancestor of a Binary Tree III

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

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

思路

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

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

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

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

最直接的想法是把缺的 root 補回來 —— 從 p 一路往上就找得到。拿到 root 之後，這題就變回 236。

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

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

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

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

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

解題方向

一、爬回 root 再套用 236

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 需要的形式。

二、只靠 parent 往上走

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：

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

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

補充

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

整個 LCA 家族：

題目	條件的差異	解法的差異
236. LCA of a Binary Tree	一般二元樹，`p`、`q` 保證存在	後序回報（原型）
235. LCA of a BST	是 BST	用值域直接往下走
1644. LCA II	`p`、`q` 可能不存在	不能提早回傳，要走完整棵樹
1650	有 parent 指標，拿不到 root	由下往上，兩條鏈求相交
1676. LCA IV	給的是一組節點	`root in nodes` 取代兩個比較

複雜度

做法一（爬回 root + 遍歷）

時間 $O (n)$ — 遍歷整棵樹
空間 $O (h)$ — 遞迴堆疊

做法二（只往上走）

時間 $O (h)$ — 兩條往上的路徑，各最多走樹高那麼多步
空間 $O (h)$ — visited 裝的是 p 到 root 的路徑

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