题目描述

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

样例

输入: 二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

说明

• 该题目与 1038 相同。

算法

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

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

时间复杂度

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

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void traverse(TreeNode* r, int &sum) {
        if (r == NULL)
            return;
        traverse(r -> right, sum);

        r -> val += sum;
        sum = r -> val;

        traverse(r -> left, sum);
    }
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        traverse(root, sum);
        return root;
    }
};