个人网站建设合同汉中建设工程招投标

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

可以做，主要还是分类讨论并找规律。

当前结点如果是左节点的话，root.val=root.val+pre.val+dfs(root.right);

如果是右结点的话，

root.val=pre.val-preval-dfs(root.left);

都和前一个结点有关系，如果找不到那个万能公式的话，就分类讨论多分几种情况。

class Solution {

    public TreeNode convertBST(TreeNode root) {

        dfs2(root,null,0,2);

        return root;

    }

    int dfs(TreeNode root){

        //对整个树求和

        if(root==null) return 0;

        return root.val+dfs(root.right)+dfs(root.left);

    }

    void dfs2(TreeNode root,TreeNode pre,int preval,int flag){

        // 左右节点分别考虑

        if(root==null) return;

        int rootval=root.val;

        if(flag==0) root.val=root.val+pre.val+dfs(root.right);

        else if(flag==1) root.val=pre.val-preval-dfs(root.left);

        else root.val+=dfs(root.right);

        dfs2(root.right,root,rootval,1);

        dfs2(root.left,root,rootval,0);

    }

 

}