题目大意：
二叉搜索子树的最大键值和
给你一棵以 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
提示：
- 每棵树最多有
40000个节点。 - 每个节点的键值在
[-4 * 10^4 , 4 * 10^4]之间。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1373
这是一道二叉搜索树（BST）的题目，我们需要采用递归方式来解题。解题时，我们判断每一个节点下面的子树是否是一颗合理的BST，如果是的话，我们还需要计算这颗子树所有节点的和。另外判断当前点是合理BST的条件很苛刻，必须同时满足以下要求：
- 当前点的值大于其左子树中的最大值。
- 当前点的值小于其右子树中的最小值。
- 左子树是BST。
- 右子树是BST。
通过上面的分析发现，我们在使用递归函数时，需要将大量信息返回给上层递归函数：
- 当前节点下方是否是BST
- 当前节点下方所有节点和
- 当前节点下方最大值
- 当前节点下方最小值
因此，我们需要建立一个Result类，来保存上述变量，同时Result也是递归函数的返回值。
递归函数中，对于任意一节点，我们首先递归求出其左子节点的返回值leftResult，以及右子节点的返回值rightResult（子节点为空时，上述返回值也为空）。这时我们可以列举出当前节点下子树为合理BST的几种情况：
- 当leftResult为空，并且rightResult为空时，当前节点为叶子节点，叶子节点本身属于合理BST，当前子树中最大值为当前节点值，最小值也是当前节点值，同时子树所有节点和也是当前节点值。
- 当leftResult为空，并且rightResult不空时，也就是当前节点下只存在右子树的情况，此时，如果右子树是BST，并且当前节点小于右子树中最小值，那么当前节点下子树是合理BST，当前子树中最大值为右子树中最大值，最小值是当前节点值，当前子树所有节点和是当前节点值加上右子树节点和。
- 当rightResult为空，并且leftResult不空时，也就是当前节点下只存在左子树的情况，此时，如果左子树是BST，并且当前节点大于左子树中最大值，那么当前节点下子树是合理BST，当前子树中最大值为当前节点，最小值是左子树中最小值，当前子树所有节点和是当前节点值加上左子树节点和。
- 当rightResult和leftResult均不空时，如果左子树是BST并且右子树也是BST，并且当前节点值大于左子树最大值，并且当前节点值小于右子树最小值，那么当前节点下是合理BST，当前子树中最大值是右子树最大值，最小值是左子树最小值，节点和是当前节点值加上左子树节点和再加上右子树节点和。
以上即是当前节点为合理BST的四种情况，在当前节点下子树是合理BST时，我们需要使用当前的子树节点和去更新全局最大值。除了上述情况之外，当前节点下都不能组成合理的BST，此时，子树的最大值，最小值以及节点和都可以重置为当前节点值（重置为任何值都无所谓，对于非法BST中的数值我们不会再使用到）。
实现代码：
class Result{ // 递归函数返回结果
int sum; // 当前节点下子树所有节点和
int min, max; // 当前子树下最小值和最大值
boolean isBST; // 当前子树是否是合理BST
public Result(int s, boolean isBST, int min, int max) {
sum = s;
this.min = min;
this.max = max;
this.isBST = isBST;
}
}
int res=0; // 返回结果
public int maxSumBST(TreeNode root) {
help(root); // 递归求解
return res;
}
Result help(TreeNode root){
// 左子节点以及右子节点返回结果
Result leftResult=null,rightResult=null;
// 左子节点不为空
if(root.left!=null){
// 递归求解左子节点返回结果
leftResult=help(root.left);
}
// 右子节点不为空
if(root.right!=null){
// 递归求解右子节点返回结果
rightResult=help(root.right);
}
// 当前节点是叶子节点
if(leftResult==null&&rightResult==null){
// 更新全局最大值
res=Math.max(res,root.val);
// 返回当前节点下子树信息：合理BST
return new Result(root.val,true,root.val,root.val);
}
// 当前节点下左右子节点都不为空
if(leftResult!=null&&rightResult!=null){
// 左右子树都是BST，并且当前节点小于右子树最小值并且大于左子树最大值
if(rightResult.isBST&&leftResult.isBST&&
root.val<rightResult.min&&root.val>leftResult.max){
// 当前节点下节点和
int sum=leftResult.sum+rightResult.sum+root.val;
// 更新全局最大值
res=Math.max(res,sum);
// 返回当前节点下子树信息：合理BST
return new Result(sum,true,leftResult.min,rightResult.max);
}
}
// 当前节点下左子节点为空，右子树是BST，并且当前节点小于右子树最小值
if(leftResult==null&&rightResult.isBST&&root.val<rightResult.min){
// 当前节点下节点和
int sum=rightResult.sum+root.val;
// 更新全局最大值
res=Math.max(res,sum);
// 返回当前节点下子树信息：合理BST
return new Result(sum,true,root.val,rightResult.max);
}
// 当前节点下右子节点为空，左子树是BST，并且当前节点大于左子树最大值
if(rightResult==null&&leftResult.isBST&&root.val>leftResult.max){
int sum=leftResult.sum+root.val;
res=Math.max(res,sum);
return new Result(sum,true,leftResult.min,root.val);
}
// 除了上述情况之外，当前节点下一定是非法BST
return new Result(root.val,false,root.val,root.val);
}
本题解法执行时间为5ms。
Runtime: 5 ms, faster than 91.91% of Java online submissions for Maximum Sum BST in Binary Tree.
Memory Usage: 58.1 MB, less than 100.00% of Java online submissions for Maximum Sum BST in Binary Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1373-maximum-sum-bst-in-binary-tree-解题思路分析/