700. Search in a Binary Search Tree

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

在一棵 BST 裡找出值等於 val 的節點，回傳以它為根的子樹；找不到就回傳 None。

這題是 BST 家族最小的一塊 —— 把它想清楚，701 插入、450 刪除、235 LCA 都是在同一條「往下走」的路徑上多做一件事。

思路

先看普通的樹

如果題目只說「樹」，沒有排序的保證，那就只能每個節點都問一次：從根開始，不是答案就左右子樹都去找。 $O (n)$ ，沒得商量。

BST 讓你每次砍掉一半

BST 的性質是「左子樹的值全部小於自己，右子樹全部大於自己」。所以在任何一個節點上比較一次，就知道答案只可能在哪一邊 —— 另一邊整棵直接丟掉，連看都不用看。

這就是二分搜尋，只是資料結構從陣列換成了樹：

	陣列的二分搜尋	BST
中點怎麼來	`(lo + hi) // 2` 算出來	樹的結構天生就給你
一次比較之後	捨棄一半的索引區間	捨棄一整棵子樹
一次比較的成本	$O (1)$	$O (1)$
總步數	$O (\log n)$	$O (h)$

差別在最後一行：陣列的二分保證 $O (\log n)$ ，因為中點是算出來的、必定對半分；BST 只能保證 $O (h)$ ，而樹可能長歪。如果依序插入 1、2、3…，整棵樹會變成一條鏈， $h = n$ ，搜尋就退化成 $O (n)$ 。

所以「BST 搜尋是 $O (\log n)$ 」這句話其實只在樹平衡時成立。 這也是 AVL、紅黑樹這些自平衡結構存在的理由。

解題方向

一、當成普通的樹搜尋

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root
        return self.searchBST(root.left, val) or self.searchBST(root.right, val)

if not root or root.val == val: return root 一行處理掉兩個終止條件 —— 找不到時 root 就是 None，剛好也是要回傳的東西。

or 的短路特性正好對應「左邊找到就不用再找右邊」。

二、利用 BST 的性質

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root
        if root.val > val:
            return self.searchBST(root.left, val)
        elif root.val <= val:
            return self.searchBST(root.right, val)

差別只有一件事：不再兩邊都遞迴，而是先比較再決定往哪一邊。

elif root.val <= val 裡的等號其實走不到 —— root.val == val 在第一行就被攔下來了，所以到這裡一定是 root.val < val。寫 <= 不會錯，但寫成 else 或 < 更能表達「剩下的情況只有一種」。

三、改寫成迴圈

上面那版是尾遞迴 —— 遞迴呼叫的結果直接回傳，沒有任何後續處理。這種形狀一定可以改成迴圈，空間從 $O (h)$ 降到 $O (1)$ ：

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        node = root
        while node and node.val != val:
            node = node.left if val < node.val else node.right
        return node

迴圈跳出時，node 要嘛是找到的節點、要嘛是 None，剛好就是答案。

「只往下走一條路」的 BST 題都可以這樣寫 —— 235 的迭代版是同一個手法。反過來說，需要「回頭處理另一邊」的樹題（例如 236 的後序回報）就沒辦法，那時候堆疊是必要的。

補充

BST 家族的共同骨架都是「比較 → 往一邊走」，差別在走到底之後做什麼：

題目	走到底之後
700	回傳節點
701. Insert into a BST	在空位掛上新節點
450. Delete Node in a BST	刪掉並用後繼節點補位
235. LCA of a BST	走到分岔點就停
270. Closest BST Value	一路記錄最接近的值

另一條線是中序遍歷：BST 的中序走訪剛好是由小到大的排序結果，98. Validate BST、230. Kth Smallest in a BST、173. BST Iterator 都是靠這個性質。整理見 Tree 遍歷模板。

複雜度

$n$ 是節點數、 $h$ 是樹高。

解法	時間	空間
一、普通樹搜尋	$O (n)$	$O (h)$ 遞迴堆疊
二、BST 遞迴	$O (h)$	$O (h)$ 遞迴堆疊
三、BST 迴圈	$O (h)$	$O (1)$

平衡時 $h = O (\log n)$ ；退化成一條鏈時 $h = n$ ，解法二三就跟解法一一樣慢了 —— 但即使如此，解法二三依然不會比解法一差。