1373. 二叉搜索子树的最大键值和

DFS+后序遍历

解题思路：最关键的地方在于二叉搜索树的判断采用什么算法进行验证，这决定着二叉树键值和的计算在什么时机。一般含有以下方法：98.验证二叉搜索树。包括后续遍历，和中序遍历，递归。

这里得出一条最关键的经验，就是二叉搜索树用后续遍历+划分子树上下界的方法比较合适。

中序遍历存在的问题

前几遍都是采用中序遍历做的，因为二叉搜索树的中序遍历序列正好是一个有序数列，用一个last变量保存前一个节点的值，当前节点如果比前一个节点小，那么说明当前节点不符合二叉搜索树。

但是中序遍历的做法有一个很大的问题在于，在比较时如果当前节点小于上一个节点值，仅仅只能说明以当前节点为根的树不是一颗搜索二叉树，但是这两个节点的相对位置并不能确定(当前节点和前一个节点谁是父亲谁是儿子，左子树还是右子树)，而有些时候即使不满足大小规则也需要继续计算树的键值和(比如当前节点是前一个节点的右子树的最左节点)。因此使用last节点比较的结果中既包含了需要继续计算键值和的，也包含需要终止计算直接返回的，而无法进一步区分。因此中序遍历仅适合于判断是否满足搜索二叉树。

上下界划分+DFS后序遍历

解题的关键在于想明白什么情况下可以统计当前树的键值和，什么情况下需要直接退出返回。直接返回的情况一共包含四种：

• 左子树不是一颗搜索二叉树
• 右子树不是一颗搜索二叉树
• 当前节点的值小于等于左子树的上界
• 当前节点的值大于等于右子树的下界

也就是说通过上下界方法，将两个节点不满足大小关系的情况，统一都在层数更高的那个节点检测出来，也就说交给父/祖先节点做大小判断。这样子的话即使是A儿子节点不满足B祖先节点的大小平衡，那么A节点可以继续计算C父节点的二叉搜索树的键值和，到B节点直接返回即可。

因此每个节点递归遍历时，都需要返回以下几个参数：①以当前节点为根的树是否是二叉搜索树②当前节点为根的树的下界③当前节点为根的树的上界④当前节点为根的树的键值和

细节

有两个地方需要注意：

• 叶子节点自成一颗二叉搜索树，需要和当前最大值进行比较
• 左子树为空或者右子树为空的节点，其上下界需要设置为当前节点的值
• 一定要遍历完左子树和右子树后，在进行统一的返回判断并退出

class Solution {
    int maxSum=0;

    public int maxSumBST(TreeNode root) {
        dfs(root);
        return maxSum;
    }
    public int[] dfs(TreeNode root) {
        if(root.left==null&&root.right==null){
            maxSum=root.val>maxSum?root.val:maxSum;
            return new int[]{1,root.val,root.val,root.val};
        }
        int[] leftsum=new int[]{1,root.val,root.val,0};
        int[] rightsum=new int[]{1,root.val,root.val,0};
        boolean valid=true;
        if(root.left!=null){
            leftsum=dfs(root.left);
            if(root.val<=leftsum[2]||leftsum[0]==0)
            valid=false;
        }
        if(root.right!=null){
            rightsum=dfs(root.right);
            if(root.val>=rightsum[1]||rightsum[0]==0)
            valid=false;
        }
        //左右子树都执行完后再跳出
        if(!valid)
        return new int[]{0,0,0,0};
        
        int ans=root.val+leftsum[3]+rightsum[3];
        maxSum=ans>maxSum?ans:maxSum;
        return new int[]{1,leftsum[1],rightsum[2],ans};
    }
}