1、前言

2、思路

这道题的意思是：将每个节点的值替换为大于或等于此节点值的和。如节点5，则它的值替换为 6 + 7 + 8 的和，加上自己 5 为26。

这道题一看就是要从右边开始遍历。我们都知道二叉搜索树从左开始中序遍历是生序，但是有意思的是，从右向左中序遍历为降序，那么我们就要依靠这种降序的思路搞事情了。

首先我们需要一个全局的 sum 记录累加和，如果节点为空则直接返回；
如果不为空，则先遍历右子树；
然后将当前节点的值加 sum，将 sum 的值赋予当前节点；
然后遍历左子树。

所以这道题也可以改成：使得每个节点的值替换为小于或等于 node.val 的值之和。解法一样。

3、代码

class Solution {

    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    private void dfs(TreeNode root){
        if(root == null){
            return;
        }

        dfs(root.right);
        sum += root.val;
        root.val = sum;
        dfs(root.left);
    }
}