1373：二叉搜索子树的最大键值和（1913 分）

力扣第 21 场双周赛第 4 题

题目

给你一棵以 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] 之间。

分析

• 递归时同时返回子树的值范围，即可判断子树是否二叉搜索树
• 是二叉搜索树就更新结果即可
• 为了方便，令空节点的值范围为 [inf,-inf]，合并左右子树的值范围时注意即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        def dfs(u):
            nonlocal res
            if not u:
                return 0,inf,-inf
            l,r = dfs(u.left),dfs(u.right)
            if l[2]<u.val<r[1]:
                res = max(res,l[0]+r[0]+u.val)
                return l[0]+r[0]+u.val,min(l[1],u.val),max(r[2],u.val)
            return 0,-inf,inf
        res = 0
        dfs(root)
        return res

119 ms