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) 空間？其核心的「線索化」是什麼概念？