Search in a Binary Search Tree

題目描述

給定一棵 BST 的根節點 root 和一個整數 val，回傳以 val 為根的子樹。如果不存在，回傳 null。

輸入: root = [4,2,7,1,3], val = 2
輸出: [2,1,3]

輸入: root = [4,2,7,1,3], val = 5
輸出: null

解題思路

比較當前值

將目標 val 和 root.val 做比較，分三種情況處理

相等

val == root.val 代表找到了，直接回傳當前節點（含整個子樹）

val 較小

val 小於 root.val，根據 BST 性質目標只可能在左子樹，走 root = root.left

val 較大

val 大於 root.val，目標只可能在右子樹，走 root = root.right

程式碼

C#

csharp

public class Solution {
    // 迭代解法（推薦）
    public TreeNode SearchBST(TreeNode root, int val) {
        while (root != null && root.val != val) {
            root = val < root.val ? root.left : root.right;
        }
        return root;
    }
 
    // 遞迴解法
    public TreeNode SearchBSTRecursive(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        return val < root.val
            ? SearchBSTRecursive(root.left, val)
            : SearchBSTRecursive(root.right, val);
    }
}

TypeScript

typescript

// 迭代解法
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
    while (root && root.val !== val) {
        root = val < root.val ? root.left : root.right;
    }
    return root;
}
 
// 遞迴解法
function searchBSTRecursive(root: TreeNode | null, val: number): TreeNode | null {
    if (!root || root.val === val) return root;
    return val < root.val
        ? searchBSTRecursive(root.left, val)
        : searchBSTRecursive(root.right, val);
}

Python

python

# 迭代解法
def searchBST(root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    while root and root.val != val:
        root = root.left if val < root.val else root.right
    return root
 
# 遞迴解法
def searchBSTRecursive(root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if not root or root.val == val:
        return root
    return searchBSTRecursive(root.left, val) if val < root.val \
        else searchBSTRecursive(root.right, val)

複雜度分析

| | Time | Space | |--|------|-------| | 迭代 | O(h) | O(1) | | 遞迴 | O(h) | O(h) |

h 是樹高。平衡 BST 中 h = O(log n)，最壞（skewed）h = O(n)。迭代 Time O(h) 是因為每步排除一個子樹、只走一個方向，最多走 h 步。迭代 Space O(1) 是因為只用一個指針；遞迴 Space O(h) 是 call stack 深度。

邊界情況

空樹：root 為 null，直接回傳 null
目標不存在：走到 null 仍未找到，回傳 null
目標是根節點：第一次比較就相等，直接回傳

圖解

2 < 4, 往左→

2 ← 找到！

→

圖表展示了搜尋 val=2 的過程：從根 4 開始，2 小於 4 所以往左走，到達節點 2 恰好等於目標值，回傳以 2 為根的子樹 [2,1,3]。只走了一步就找到。

進階觀點

💡面試追問

Q: 面試中該寫迭代還是遞迴？ A: 優先寫迭代。O(1) 空間、沒有 stack overflow 風險、程式碼也很短。但要能口頭說明遞迴寫法，展示你理解兩種思路。

Q: BST 搜尋和 Binary Search 的關係是什麼？ A: 本質相同 — 每步根據大小關係排除一半搜尋空間。BST 中序遍歷等於排序陣列，所以 BST 搜尋就是在這個隱式排序序列上做 Binary Search。平衡 BST 保證 O(log n)，和 Binary Search 相同。

變體題：LC 701 Insert into a BST（插入）、LC 450 Delete Node in a BST（刪除，更複雜）。

理解測驗

🤔 為什麼 BST 搜尋比普通二元樹搜尋快？

🤔 BST 搜尋的最壞時間複雜度是什麼？何時發生？