LeetCode所有大于等于节点的值之和

剑指 Offer II 054. 所有大于等于节点的值之和

给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

提醒一下，二叉搜索树满足下列约束条件：

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

输入：root = [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]

来源：力扣（LeetCode）

二叉搜索树的性质就是左子树小于根节点，右子树大于根节点。
所以它的中序遍历结果就是递增的，而题目里面要求每个节点是大于它的节点和它本身的和，那就得从最大的开始算起，最大的节点的值就是它本身，然后下一个节点再进行累加。

如果就按中序遍历来进行计算，就需要遍历多次，而且需要记录每次遍历的顺序。

所以反序中序遍历即可，让节点值大的先进行计算，这样只需要一遍就行。

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root!=null){
            convertBST(root.right);
            sum+=root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

需要注意的是，每个节点的值修改成sum，sum应该是全局变量。

反序的中序遍历就是先遍历右子树，再是根节点，然后再是左子树。