700. Search in a Binary Search Tree

📘 題目敘述

給你一個二元搜尋樹（Binary Search Tree, BST）的根節點 root，以及一個整數 val。

請在 BST 中尋找節點值等於 val 的節點，並回傳以該節點為根的子樹。

如果找不到值等於 val 的節點，則回傳 null。

條件限制

• 樹中節點的數量在範圍 [1, 5000]
• 1 <= Node.val <= 10^7
• root 是一棵二元搜尋樹
• 1 <= val <= 10^7

🧠 解題思路

這題的關鍵是利用 BST 的性質：

• 對任何一個節點 root：
  • 左子樹所有值都小於 root->val
  • 右子樹所有值都大於 root->val

所以我每次站在一個節點，只要比較 val 和 root->val：

• 如果相等：找到答案，直接回傳這個節點
• 如果 val 比它小：答案只可能在左子樹，往左遞迴
• 如果 val 比它大：答案只可能在右子樹，往右遞迴

一路走下去，直到找到或走到空節點。

🪜 主要流程步驟

1. 如果 root 是空，代表找不到

只要走到 root == nullptr，就代表這條路徑已經沒有節點了，直接回傳 nullptr。

2. 如果 root->val == val，直接回傳 root

在 BST 搜尋中，一旦命中就是答案，回傳這個節點（也等於回傳以它為根的子樹）。

3. val 比 root->val 小就往左，比它大就往右

利用 BST 性質縮小搜尋範圍：

• val < root->val → searchBST(root->left, val)
• 否則 → searchBST(root->right, val)

⏱️ 複雜度

• 時間複雜度：O(h)，h 是樹高，每次只往一邊走。平衡 BST 是 O(log n)，最壞鏈狀是 O(n)。
• 空間複雜度：O(h)，遞迴呼叫堆疊深度等於走過的高度。

💻 程式碼實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) {
            return nullptr;
        }
        if (root->val == val) {
            return root;
        } else if (val < root->val) {
            return searchBST(root->left, val);
        } else {
            return searchBST(root->right, val);
        }
    }
};

🔗 題目連結

https://leetcode.com/problems/search-in-a-binary-search-tree/