【递归】 538把二叉搜索树转换为累加树

题目

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
输入: 原始二叉搜索树:
5
/
2 13
输出: 转换为累加树:
18
/
20 13

思路

二叉搜索树，要想到中序遍历。写出最后的结果集合，每个数字的值就是后者所有的累加。因此就是反向中序遍历，并把每次的节点值进行累加。

代码

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
int sum = 0;
public TreeNode convertBST(TreeNode root) {
    if(root==null){
        return null;
    }
    convertBST(root.right);
    sum = sum+root.val;
    root.val = sum;
    convertBST(root.left);
    return root;
}