Medium
538. Convert BST to Greater Tree
treedepth-first-searchbinary-search-treebinary-tree
解題說明
Convert BST to Greater Tree
題目描述: 給定一棵二元搜尋樹(BST),將其轉換為「Greater Tree」——每個節點的新值等於原始 BST 中所有大於等於該節點值的節點值之和。
解題思路: 利用 BST 的性質,使用反向中序遍歷(右 → 根 → 左)。在標準中序遍歷中,節點按升序訪問;反向中序則按降序訪問。
- 維護一個累加變數
sum,初始為 0。 - 先遞迴訪問右子樹(更大的值先處理)。
- 累加當前節點值:
sum += node->val,然後更新節點值為sum。 - 再遞迴訪問左子樹。
這樣每個節點的新值自然就是所有大於等於它的值的總和。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每個節點恰好訪問一次。
空間複雜度:O(h) — 遞迴堆疊深度為樹的高度 h。最壞情況(鏈狀樹)O(n),平衡樹 O(log n)。
虛擬碼
1. Initialize sum = 0 2. Define reverseInorder(node, sum): a. If node is null, return b. reverseInorder(node.right, sum) // right first (larger values) c. sum += node.val d. node.val = sum e. reverseInorder(node.left, sum) // then left (smaller values) 3. Call reverseInorder(root, sum) 4. Return root
其他解法
Morris 遍歷(O(1) 空間):使用反向 Morris 中序遍歷,透過暫時修改樹的右指標(threading)實現不用遞迴和堆疊的 O(1) 空間遍歷。時間 O(n),空間 O(1)。適合空間敏感場景,但程式碼較複雜。
迭代 + 堆疊:使用顯式堆疊模擬反向中序遍歷。先不斷走右子樹入堆疊,彈出時處理節點值,再轉向左子樹。時間 O(n),空間 O(h)。與遞迴等效但避免了系統遞迴深度限制。
延伸思考
- 此題與 LeetCode 1038(Convert BST to Greater Tree)完全相同,為什麼 BST 的反向中序遍歷能正確計算累加和?
- 若不是 BST 而是普通二元樹,能否用類似方法解題?需要什麼改變?
- Morris 遍歷如何在不破壞樹結構的前提下實現 O(1) 空間?其核心的「線索化」是什麼概念?