题目描述

给出二叉 搜索 树的根结点，该二叉树的结点值各不相同，修改二叉树，使每个结点的新值为原树中大于或等于当前结点值的结点的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 结点的左子树仅包含键 小于 结点键的结点。
• 结点的右子树仅包含键 大于 结点键的结点。
• 左右子树也必须是二叉搜索树。

样例

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

限制

• 树中的结点数介于 1 和 100 之间。
• 每个结点的值介于 0 和 100 之间。
• 给定的树为二叉搜索树。

说明

• 该题目与 538 相同。

算法

(逆中序遍历) $O(n)$

1. 对二叉搜索树进行逆中序遍历，遍历过程中，记录之前各个结点的累加值，然后追加到当前结点上即可。

时间复杂度

• 每个结点仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(h)$ 的空间存储系统栈，其中 $h$ 为树的最大高度。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void solve(TreeNode *root, int& t) {
        if (!root) return;

        solve(root->right, t);
        root->val += t;
        t = root->val;
        solve(root->left, t);
    }

    TreeNode* bstToGst(TreeNode* root) {
        int t = 0;
        solve(root, t);
        return root;
    }
};