🔗 🟡 1038. Binary Search Tree to Greater Sum Tree 1375

tags: Weekly Contest 135 DFS 樹(Tree) 二元樹(Binary Tree) BST

題意

給定一個 二元搜尋樹(Binary Search Tree, BST) 的根節點 rootroot，將其每個節點的值替換為樹中所有大於或等於該節點值的節點值之和。

二元搜尋樹滿足以下條件：

  • 節點的左子樹只包含鍵值小於該節點鍵值的節點。
  • 節點的右子樹只包含鍵值大於該節點鍵值的節點。
  • 左右子樹也必須是二元搜尋樹。

約束條件

  • 1≤n≤1001 \leq n \leq 100 ，其中 nn 為樹中節點的數量。
  • 0≤Node.val≤1000 \leq \text{Node.val} \leq 100。
  • 樹中所有節點的值都是 唯一 的。

思路：反向的中序遍歷

根據 BST 的性質，大於等於某個節點值的節點總是存在於該節點的右子樹上，因此可以使用 反向的中序遍歷 ，先遞迴右子樹，然後處理當前節點，最後遞迴左子樹。這樣就能按照從大到小的順序遍歷。

在遞迴過程中，維護一個變數 ss 來累加大於或等於該節點值的節點值之和，並將該節點值替換為 ss。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)，每個節點訪問一次。
  • 空間複雜度：O(n)\mathcal{O}(n)，遞迴深度最差情況下為 O(n)\mathcal{O}(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        s = 0
        def dfs(node: TreeNode) -> None:
            if node is None:
                return
            nonlocal s
            dfs(node.right)
            s += node.val # sum of all nodes >= node.val
            node.val = s
            dfs(node.left)
        dfs(root)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int s = 0;
        function<void(TreeNode*)> dfs = [&](TreeNode* node) {
            if (node == nullptr) return;
            dfs(node->right);
            s += node->val;
            node->val = s;
            dfs(node->left);
        };
        dfs(root);
        return root;
    }
};

類題

寫在最後

Cover photo is generated by @たろたろ, thanks for their work!