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

树

shenjin考试3.19

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

解：
5 => 18
/\ => /\
2 13 => 20 13
找规律，右中左是递增的，按照这个顺序遍历并相加,用int& sum来递归。

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