Leetcode538. 把二叉搜索树转换为累加树

题目

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

例如：

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

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

思路

中序遍历两遍，第一遍求和，第二遍把和赋予给当前节点，然后和减去当前节点值。

C++代码

class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        calcuateSum(root);
        transferToGreaterTree(root);
        return root;
    }
    
    void calcuateSum(TreeNode* root) {
        if (root == NULL) return;
        calcuateSum(root->left);
        sum += root->val;
        calcuateSum(root->right);
    }
    void transferToGreaterTree(TreeNode* root) {
        if (root == NULL) return;
        transferToGreaterTree(root->left);
        int val = root->val;
        root->val = sum;
        sum -= val;
        transferToGreaterTree(root->right);
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree