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

给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。

二叉搜索树的定义如下：

• 任意节点的左子树中的键值都 小于 此节点的键值。
• 任意节点的右子树中的键值都 大于 此节点的键值。
• 任意节点的左子树和右子树都是二叉搜索树。

示例 1：

输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出：20
解释：键值为 3 的子树是和最大的二叉搜索树。

示例 2：

输入：root = [4,3,null,1,2]
输出：2
解释：键值为 2 的单节点子树是和最大的二叉搜索树。

示例 3：

输入：root = [-4,-2,-5]
输出：0
解释：所有节点键值都为负数，和最大的二叉搜索树为空。

示例 4：

输入：root = [2,1,3]
输出：6

示例 5：

输入：root = [5,4,8,3,null,6,3]
输出：7

提示：

• 每棵树有 1 到 40000 个节点。
• 每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，这题比较简单，其实只要搞懂两件事：是不是二叉搜索树，最大和是多少

方法：DFS

是不是二叉搜索树？

1. 左右子树都是二叉搜索树

2. 根节点的值需要大于左子树的最大值，小于右子树的最小值

3. 综上需要记录子树的 最大最小值以及是否二叉搜索树

最大和是多少？

1. 是二叉搜索树，才有必要把和计入答案

2. 需要知道子树和。当前树和 = 左子树和+右子树和+当前值

3. 综上需要记录子树和

所以每个节点返回时，需要提供四个信息：[最小值，最大值，和，是不是二叉搜索树]

class Solution {
    public int maxSumBST(TreeNode root) {
        getBSTMax(root);
        return res;
    }
 
    int res = 0;
    private int[] getBSTMax(TreeNode root){
        if(root==null) return new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE,0,1};
        int[] ans = new int[4];
        int[] left = getBSTMax(root.left);
        int[] right = getBSTMax(root.right);
        if(left[3]==1&&right[3]==1&&left[1]0]>root.val){
            ans = new int[]{Math.min(left[0],root.val),Math.max(right[1],root.val),root.val+left[2]+right[2],1};
            res = Math.max(res,ans[2]);
        }
        return ans;
    }
}