Leetcode 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
提示：
每棵树最多有40000 个节点。
每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。
解题思路
这个问题和Leetcode 1372：二叉树中的最长交错路径类似，定义函数f(root)f(root)f(root)返回以root为根的树是不是二叉树，并且返回键值和（并不是返回二叉树的最大键值和）。
如果左子树是二叉树并且root.left.val < root.val，说明当前root为根可能是一颗二叉树，那么我们要将左子树的键值和添加；否则，当前root为根的子树必然不是二叉树。如果右子树是二叉树并且root.right.val > root.val，说明当前root为根可能是一颗二叉树，那么我们要将右子树的键值和添加；否则，当前root为根的子树必然不是二叉树。
判断完上述两种条件后，如果以root为根的树为二叉树，我们需要记录当前键值和。最后返回以root为根是不是二叉树，并且返回键值和。
class Solution:
def maxSumBST(self, root: TreeNode) -> int:
maxv = 0
def dfs(root):
nonlocal maxv
if not root: return True, 0
res = [True, root.val]
if root.left:
left = dfs(root.left)
if left[0] and root.left.val < root.val:
res[1] += left[1]
else:
res[0] = False
if root.right:
right = dfs(root.right)
if right[0] and root.val < root.right.val:
res[1] += right[1]
else:
res[0] = False
if res[0]: maxv = max(maxv, res[1])
return res
dfs(root)
return maxv
我将该问题的其他语言版本添加到了我的GitHub Leetcode
如有问题，希望大家指出！！！
作者：coordinate_blog
