1038. 从二叉搜索树到更大和树

给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
�
提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

示例 1：
输入：[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：
输入：root = [0,null,1]
输出：[1,null,1]

示例 3：
输入：root = [1,0,2]
输出：[3,3,2]

示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
�

累加树的节点值该怎么计算呢？
节点8 ：因没有比其值大的节点，累加树的节点值 = 8
节点7：因节点8的值比其大，累加树的节点值 = 7 + 8 = 15
节点6：因节点7，8的值比其大，累加树的节点值 = 6 + 7 + 8 = 21
节点5：因节点6，7，8的值比其大，累加树的节点值 = 5 + 6 + 7 + 8 = 26
节点4：因节点5，6，7，8的值比其大，累加树的节点值 = 4 + 5 + 6 + 7 + 8 = 30
节点3：因节点4，5，6，7，8的值比其大，累加树的节点值 = 3 + 4 + 5 + 6 + 7 + 8 = 33
节点2：因节点3，4，5，6，7，8的值比其大，累加树的节点值 = 2 + 3 + 4 + 5 + 6 + 7 + 8 = 35
节点1：因节点2，3，4，5，6，7，8的值比其大，累加树的节点值 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
节点0：因节点1，2，3，4，5，6，7，8的值比其大，累加树的节点值 = 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36

如果从节点8往节点0的顺序遍历，那么实际上每遍历到一个节点，则将已遍历过的节点值累加上当前节点值即是目标值

/**
 * 二叉搜索树的中序遍历是一个升序序列
 *
 * @param node
 * @param valList
 */
private void inOrder(TreeNode node, List<Integer> valList) {
    if (node == null) {
        return;
    }
    inOrder(node.left, valList);
    valList.add(node.val);
    inOrder(node.right,valList);
}

二叉搜索树的中序遍历是一个升序序列，那么怎么得到一个降序序列呢？
�先左子树，然后根节点，最后右子树是升序序列，那么先右子树，然后根节点，最后左子树则是降序序列

/**
 * 二叉搜索树的逆向中序遍历是一个降序序列
 *
 * @param node
 * @param valList
 */
private void inOrder(TreeNode node, List<Integer> valList) {
    if (node == null) {
        return;
    }
    inOrder(node.right,valList);
    valList.add(node.val);
    inOrder(node.left, valList);
}

�
那么在逆序中序遍历时，借用一个变量累加已经遍历过的节点值，并且将累加值重新赋值给当前节点即可

public TreeNode bstToGst(TreeNode root) {
    inOrder(root);
    return root;
}
int sum = 0;
private void inOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrder(node.right);
    sum += node.val;
    node.val = sum;
    inOrder(node.left);
}