題目描述: 給定一棵二元搜尋樹(BST),將其轉換為「Greater Tree」——每個節點的新值等於原始 BST 中所有大於等於該節點值的節點值之和。
解題思路: 利用 BST 的性質,使用反向中序遍歷(右 → 根 → 左)。在標準中序遍歷中,節點按升序訪問;反向中序則按降序訪問。
sum,初始為 0。sum += node->val,然後更新節點值為 sum。這樣每個節點的新值自然就是所有大於等於它的值的總和。
時間複雜度: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)。與遞迴等效但避免了系統遞迴深度限制。