原题链接:
https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/
蛮综合的一道题
尤其是边界情况的条件处理比较巧妙
当前bst判断不成立时 将当前子树的最小值设置为inf 最大值设置-inf返回
则接下来任意 包含该子树的判断 均不会满足 左子树最大值<node.val<右子树最小值 这一条件 即不会更新ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# 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:
    """
    先判断 左子树 右子树 是否为 bst
    如果左右子树均为bst
        看左子树的最大值是否小于 root.val
        看右子树的最小值是否大于 root.val
    如果成立 则证明当前整棵树 也是一棵bst 更新答案 ans = max(ans,root.val + 左子树的总和 + 右子树总和)
    """

    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        ans = 0
        inf = 10 ** 8

        def dfs(node: TreeNode) -> []:
            """
            返回三个数
            当前子树总和 最小值 最大值
            """
            # 左子树
            # sum: 初始时左子树和为0
            # 最小值: 当子树不存在时 默认返回根节点的值
            # 最大值: 最大值初始化为负无穷
            left = [0, node.val, -inf]

            # 右子树 同理
            right = [0, inf, node.val]

            if node.left:
                left = dfs(node.left)

            if node.right:
                right = dfs(node.right)

            nonlocal ans
            # 如果左子树的最大值小于 < 根节点 < 右子树最小值
            # 当前的树为bst 更新结果
            if left[2] < node.val < right[1]:
                s = node.val + left[0] + right[0]
                ans = max(ans, s)
                # 当前子树的总和 左子树的最小值(即整棵树的最小值)  右子树的最大值(即整棵树的最大值)
                return [s,left[1],right[2]]

            # 当前子树非bst
            # 则将当前和置为-inf 最小值inf 最大值置为-inf
            # 这样的话 在接下来的任何判断中凡是包含该子树的树 都不会成立 即不会对ans进行更新
            return [-inf,inf,-inf]

        dfs(root)

        return ans