題目描述:給定一棵二元搜尋樹(BST)的根節點和範圍 [low, high],修剪樹使得所有節點的值都在 [low, high] 範圍內。修剪後的樹仍然是有效的 BST。
解題思路:利用 BST 的性質進行遞迴修剪:
low,則當前節點及其所有左子樹都不在範圍內,遞迴處理右子樹。high,則當前節點及其所有右子樹都不在範圍內,遞迴處理左子樹。時間複雜度: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)。迭代法不需要遞迴堆疊,但程式碼較長且不夠直觀。