235. Lowest Common Ancestor of a Binary Search Tree

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

跟 236 一樣要找最近共同祖先，差別只有一個：這棵樹是 BST。

思路

236 那份通用的後序解法直接拿來用就會過 —— 做法完全一模一樣，BST 的性質一點都沒用到。但那樣就浪費了這題的條件。

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

站在 node 上有三種情況：

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

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

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

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

解題方向

BST 專屬：沿著值域往下走

# 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 題的通則：只要每一步都能靠比較決定往哪一邊走，就不需要遞迴，跟二分搜尋是同一個形狀。

通用解法（也會過）

236 的後序版對 BST 一樣正確，只是慢一些：

# 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	一般二元樹，`p`、`q` 保證存在	後序回報（原型）
235	是 BST	用值域直接往下走
1644. LCA II	`p`、`q` 可能不存在	不能提早回傳，要走完整棵樹
1650. LCA III	有 parent 指標，拿不到 root	退化成兩條鏈結串列求相交
1676. LCA IV	給的是一組節點	`root in nodes` 取代兩個比較

其他「靠值域往下走」的 BST 題：270. Closest BST Value、700. Search in a BST、701. Insert into a BST、98. Validate BST。

複雜度

BST 版

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

通用版

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

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