解題說明
Search in a Binary Search Tree
題目描述：給定二元搜尋樹（BST）的根節點與目標值 val，回傳以 val 為根的子樹；若不存在則回傳 null。
解題思路：利用 BST 性質：左子樹所有節點 < 根，右子樹所有節點 > 根。從根出發：若當前值等於 val 回傳當前節點；若 val 較小則往左子樹遞迴；若較大則往右子樹遞迴。迭代版本用 while 迴圈代替遞迴，避免函式呼叫開銷。
C++ 解法
複雜度分析
時間複雜度：O(h) — h 為樹高；平衡 BST 為 O(log n)，最壞（退化成鏈）為 O(n)。
空間複雜度：O(h) — 遞迴呼叫堆疊深度等於樹高；迭代版本為 O(1)。
虛擬碼
1. If root is null: return null 2. If root.val == val: return root 3. If val < root.val: return searchBST(root.left, val) 4. Else: return searchBST(root.right, val) Iterative version: 1. While root is not null: a. If root.val == val: return root b. If val < root.val: root = root.left c. Else: root = root.right 2. Return null
其他解法
迭代（Iterative）：用 while 迴圈代替遞迴，每次將 root 更新為左或右子節點。空間複雜度降至 O(1)，在樹很深時更節省堆疊空間，是生產環境較推薦的寫法。
中序遍歷後二分搜尋：將整棵樹中序遍歷成有序陣列，再用二分法搜尋 val。時間 O(n)、空間 O(n)，效率遠不如直接利用 BST 性質。
延伸思考
- 如何在 BST 中插入一個新節點（LC 701）？
- 如何刪除 BST 中的指定節點（LC 450），並保持 BST 性質？
- 若 BST 退化成鏈結串列（最壞情況），如何透過 AVL 或紅黑樹自動平衡來保持 O(log n) 搜尋效率？