給定一棵 BST 的根節點，將每個節點的值替換為原 BST 中所有大於或等於該節點值的節點值之和。
Example:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Intuition
TIP
反向中序遍歷（右 -> 根 -> 左）就是從大到小遍歷，累加即可。
- BST 中序遍歷（左 -> 根 -> 右）得到遞增序列
- 反向中序遍歷（右 -> 根 -> 左）得到遞減序列
- 維護一個累加和，每到一個節點就加上累加和，更新節點值
Approaches
1. Reverse Inorder (recursive) — O(n) / O(h)
- Idea: 反向中序遍歷，用全域變數累加，每個節點更新為累加和
- Time:
O(n) - Space:
O(h)，h 為樹高
class Solution {
private var sum = 0
fun convertBST(root: TreeNode?): TreeNode? {
sum = 0
reverseInorder(root)
return root
}
private fun reverseInorder(node: TreeNode?) {
if (node == null) return
reverseInorder(node.right)
sum += node.`val`
node.`val` = sum
reverseInorder(node.left)
}
}⭐ 2. Reverse Inorder (iterative) — O(n) / O(h)
- Idea: 用堆疊模擬反向中序遍歷，先一路向右，然後處理當前節點，再轉左
- Time:
O(n) - Space:
O(h)
class Solution {
fun convertBST(root: TreeNode?): TreeNode? {
val stack = ArrayDeque<TreeNode>()
var sum = 0
var current = root
while (current != null || stack.isNotEmpty()) {
while (current != null) {
stack.addLast(current)
current = current.right
}
current = stack.removeLast()
sum += current.`val`
current.`val` = sum
current = current.left
}
return root
}
}Morris Traversal (O(1) space)
可以用 Morris 遍歷達到 O(1) 空間，但程式碼較複雜，面試中反向中序遍歷已經足夠。Morris 遍歷利用葉節點的空指標建立臨時鏈接，省去堆疊的空間開銷。
🔑 Takeaways
- Pattern: 反向中序遍歷（右 -> 根 -> 左）是 BST 從大到小遍歷的標準方式
- Key trick: 將中序遍歷的方向反轉（左右互換），配合累加變數即可完成 Greater Tree 轉換