本文共 1601 字，大约阅读时间需要 5 分钟。

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

解题思路

这个问题和类似，定义函数$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

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/104762036 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！