Leetcode 1373. Maximum Sum BST in Binary Tree [Python]

本文主要是介绍Leetcode 1373. Maximum Sum BST in Binary Tree [Python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

初期版本TLE在第55个TC。判断BST的函数似乎得当作模版记下来。

# 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: TreeNode) -> int:if not root:return 0curres = 0if self.isBST(root):curres = self.sumBST(root)return max(curres, max(self.maxSumBST(root.left), self.maxSumBST(root.right)))            def isBST(self, root):return self.isBSThelper(root, float('-inf'), float('inf'))def isBSThelper(self, root, curmin, curmax):if not root:return Trueif root.val <= curmin or root.val >= curmax:return Falsereturn self.isBSThelper(root.left, curmin, root.val) and self.isBSThelper(root.right, root.val, curmax)def sumBST(self, root):if not root:return 0return root.val + self.sumBST(root.left) + self.sumBST(root.right)      

改进一下

class Solution:def maxSumBST(self, root: TreeNode) -> int:self.res = float('-inf')def dfs(root):if not root: return float('inf'), float('-inf'), 0 #min,max,sumleftmin, leftmax, leftsum = dfs(root.left)rightmin, rightmax, rightsum = dfs(root.right)if leftmax < root.val < rightmin: # valid BSTself.res = max(self.res, root.val + leftsum + rightsum)return min(root.val, leftmin), max(root.val , rightmax), root.val + leftsum + rightsumelse:return float('-inf'), float('inf'), 0dfs(root)return max(self.res, 0)

这篇关于Leetcode 1373. Maximum Sum BST in Binary Tree [Python]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---