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);
}
}