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

传送门

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

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

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

二叉树是BST，那么root的右边都比root大，累加右边所有节点的和就行，
遍历方向是： 右->中->左 (反向中序遍历)

但是注意的是，如果sum不是全局变量，而是作为helper的参数，在 helper(xx, sum) 递归之后，sum += root.val的sum还是0，没有在上面递归里面得到更新。

int sum = 0;
public TreeNode convertBST(TreeNode root) {
    helper(root);
    return root;
}
void helper(TreeNode root) {
    if (root == null) return ;

    helper(root.right);
    //sum += root.val;
    //root.val = sum;
    root.val = (sum += root.val);//可以代替上面两行
    helper(root.left);
}