Leetcode 1373:二叉搜索子树的最大键值和(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1373:二叉搜索子树的最大键值和(超详细的解法!!!)

in leetcode with 0 comment

给你一棵以 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

提示:

解题思路

这个问题和Leetcode 1372:二叉树中的最长交错路径类似,定义函数$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

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses