Description
給定一棵 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#
反向中序遍歷（右 -> 根 -> 左）就是從大到小遍歷，累加即可。
- BST 中序遍歷（左 -> 根 -> 右）得到遞增序列
- 反向中序遍歷（右 -> 根 -> 左）得到遞減序列
- 維護一個累加和，每到一個節點就加上累加和，更新節點值
Approaches#
1: 反向中序遍歷（遞迴）#
- 概念: 反向中序遍歷，用全域變數累加，每個節點更新為累加和
- 時間複雜度:
O(n) - 空間複雜度:
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: 反向中序遍歷（迭代）#
- 概念: 用堆疊模擬反向中序遍歷，先一路向右，然後處理當前節點，再轉左
- 時間複雜度:
O(n) - 空間複雜度:
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 遍歷法（O(1) 空間）
可以用 Morris 遍歷達到 O(1) 空間，但程式碼較複雜，面試中反向中序遍歷已經足夠。Morris 遍歷利用葉節點的空指標建立臨時鏈接，省去堆疊的空間開銷。
🔑 Takeaways#
- Pattern: 反向中序遍歷（右 -> 根 -> 左）是 BST 從大到小遍歷的標準方式
- 關鍵技巧: 將中序遍歷的方向反轉（左右互換），配合累加變數即可完成 Greater Tree 轉換