难度: Hard
给你一棵以 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] 之间。运行时间: 173 ms
内存: 34.7 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxSumBST(self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(root):
nonlocal ans
if not root.left:
if not root.right:
ans = max(ans, root.val)
return root.val, root.val, root.val
else:
sum2, Rmin, Rmax = dfs(root.right)
if sum2 >= - 10 ** 10 and root.val < Rmin:
ans = max(ans, root.val + sum2)
return root.val + sum2, root.val, Rmax
else:
return float("-inf"), -1, -1
elif not root.right:
sum1, Lmin, Lmax = dfs(root.left)
if sum1 >= - 10 ** 10 and root.val > Lmax:
ans = max(ans, root.val + sum1)
return root.val + sum1, Lmin, root.val
else:
return float("-inf"), -1, -1
else:
sum1, Lmin, Lmax = dfs(root.left)
sum2, Rmin, Rmax = dfs(root.right)
if sum1 >= - 10 ** 10 and sum2 >= - 10 ** 10 and Lmax < root.val < Rmin:
ans = max(ans, root.val + sum1 + sum2)
return root.val + sum1 + sum2, Lmin, Rmax
else:
return float("-inf"), -1, -1
dfs(root)
return ans
本题解采用深度优先搜索（DFS）方法来找出具有最大键值和的二叉搜索子树。对于每个节点，我们检查其是否能形成一个二叉搜索树（BST）。具体来说，DFS函数返回一个三元组：(子树的和, 子树的最小值, 子树的最大值)。若某个子树不是BST，我们使用一个非常小的标记值（float('-inf')）来标记其和，这样其父节点就不会错误地认为它可以形成BST。在递归过程中，我们更新全局变量ans来保持迄今为止找到的最大键值和。这种方法确保每个节点最多被访问一次。
时间复杂度: O(n)
空间复杂度: O(h)，其中h是树的高度
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxSumBST(self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(root):
nonlocal ans
if not root.left:
if not root.right:
ans = max(ans, root.val) # Update max sum with the value of the leaf
return root.val, root.val, root.val # Leaf is a valid BST
else:
sum2, Rmin, Rmax = dfs(root.right)
if sum2 >= - 10 ** 10 and root.val < Rmin:
ans = max(ans, root.val + sum2)
return root.val + sum2, root.val, Rmax
else:
return float("-inf"), -1, -1
elif not root.right:
sum1, Lmin, Lmax = dfs(root.left)
if sum1 >= - 10 ** 10 and root.val > Lmax:
ans = max(ans, root.val + sum1)
return root.val + sum1, Lmin, root.val
else:
return float("-inf"), -1, -1
else:
sum1, Lmin, Lmax = dfs(root.left)
sum2, Rmin, Rmax = dfs(root.right)
if sum1 >= - 10 ** 10 and sum2 >= - 10 ** 10 and Lmax < root.val < Rmin:
ans = max(ans, root.val + sum1 + sum2)
return root.val + sum1 + sum2, Lmin, Rmax
else:
return float("-inf"), -1, -1
dfs(root)
return ans
在二叉搜索树（BST）中，任一节点的左子树中所有节点的值必须小于该节点的值，右子树中所有节点的值必须大于该节点的值。因此，在判断一个节点及其子树是否构成BST时，不仅需要检查该节点的直接子节点，也需要确认左子树中的最大值小于该节点的值，且右子树中的最小值大于该节点的值。这样可以确保整个子树都符合BST的性质。
使用float('-inf')来标记非BST子树的和是为了在计算最大键值和时排除非BST子树。此做法不会影响算法的正确性，即使树中包含负数值节点。因为在计算过程中，任何包含非BST部分的和都被标记为float('-inf')，这个值在比较中总是小于任何正数或负数的和，因此不会被错误地考虑为可能的最大和。此外，只有完全符合BST条件的子树的和才会被用于更新最大和。
在递归处理中，如果节点值为null，即该节点不存在，通常表现为其父节点的left或right属性为null。在DFS函数的实现中，当一个节点不存在时（例如，root.left或root.right为null时），不会进入该节点的DFS递归调用。因此，不存在节点的情况已经隐含在递归调用的条件检查中，不需要额外的null值检查。这种处理方式简化了代码且不会影响函数的正确执行。
在二叉树中，叶子节点是没有子节点的节点。对于叶子节点，它本身就满足二叉搜索树的条件且其键值和就是节点本身的值。因此，对于叶子节点，可以直接返回其值作为键值和，并且更新全局的最大键值和。对于非叶子节点，需要检查其左右子树是否为BST，并确保左子树的最大值小于当前节点值，右子树的最小值大于当前节点值，才能将左右子树的和加上当前节点的值作为整个子树的和。这种区分处理是因为非叶子节点需要整合其子节点的信息来判断整个子树是否符合BST的条件。