538. 把二叉搜索树转换为累加树 (opens new window)

1.反序中序遍历

分析：反向中序遍历，因为题目给的树是一棵二叉搜索树，因此每一个节点需要加上的值为其右子树的累加和，以及父亲节点的累加和。

先遍历右子树，拿到最新的累加和之后，更新当前节点的权值以及累加和(需要一个变量保存中间值)，然后遍历左子树。

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root==null) return root;
        dfs(root);
        return root;
    }
    public void dfs(TreeNode root){
        if(root.right!=null) dfs(root.right);
        int temp=root.val;
        root.val+=sum;
        sum=sum+temp;
        if(root.left!=null) dfs(root.left);
    }
}