Medium
669. Trim a Binary Search Tree
treedepth-first-searchbinary-search-treebinary-tree
解題說明
Trim a Binary Search Tree
題目描述：給定一棵二元搜尋樹（BST）的根節點和範圍 [low, high]，修剪樹使得所有節點的值都在 [low, high] 範圍內。修剪後的樹仍然是有效的 BST。
解題思路：利用 BST 的性質進行遞迴修剪：
- 若當前節點值小於
low，則當前節點及其所有左子樹都不在範圍內，遞迴處理右子樹。 - 若當前節點值大於
high，則當前節點及其所有右子樹都不在範圍內，遞迴處理左子樹。 - 若當前節點值在範圍內，遞迴修剪左右子樹。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個節點最多被訪問一次。
空間複雜度：O(n) — 遞迴堆疊深度在最壞情況下（退化樹）為 O(n)，平衡樹為 O(log n)。
虛擬碼
1. If root is null, return null 2. If root.val < low, return trimBST(root.right, low, high) 3. If root.val > high, return trimBST(root.left, low, high) 4. root.left = trimBST(root.left, low, high) 5. root.right = trimBST(root.right, low, high) 6. Return root
其他解法
迭代法：先找到根節點在範圍內的節點，然後分別處理左右子樹中超出範圍的部分。具體來說，對左子樹不斷檢查：若左子節點的值小於 low，用其右子節點取代。右子樹同理。時間 O(n)，空間 O(1)。迭代法不需要遞迴堆疊，但程式碼較長且不夠直觀。
延伸思考
- 如果輸入不是 BST 而是普通二元樹，修剪方式會有何不同？
- 修剪操作會改變樹的高度嗎？最壞情況下高度會如何變化？
- 能否用迭代方式實現？與遞迴相比有何優勢？