力扣538 把二叉搜索树转换为累加树

题目：

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
    节点的左子树仅包含键小于节点键的节点。
    节点的右子树仅包含键大于节点键的节点。
    左右子树也必须是二叉搜索树。

示例：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

思路：

　　换一个角度来看，这是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]。数组大家都知道怎么遍历，从后向前，挨个累加就完事了，那么换成了二叉搜索树，知道如何遍历这个二叉树，也就迎刃而解了，从树中可以看出累加的顺序是右中左，所以需要反中序遍历这个二叉树，然后顺序累加。

class Solution {
    int sum;
    public TreeNode convertBST(TreeNode root) {
        //题目：使每个节点node的新值等于原树中大于或等于node.val的值之和。
        //比如：node->4,则node的新值应该是比4大和相等的所有节点值的总和4+5+6+7+8=30
        //找在其右侧所有节点的和+自身值
        sum=0;
        convertBST1(root);
        return root;
    }

    public void convertBST1(TreeNode root){
        if(root==null){
            return;
        }
        convertBST1(root.right);
        sum+=root.val;//按反中序顺序遍历相加：右中左
        root.val=sum;//赋值给当前节点
        convertBST1(root.left);
    }    
}