解題說明
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) 搜尋效率?