1373. 二叉搜索子树的最大键值和

1373. 二叉搜索子树的最大键值和

# 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 __init__(self):
        self.maxSum = 0

    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.findMaxMinSum(root)
        return self.maxSum


    def findMaxMinSum(self, root: TreeNode):
        """

        :param root:
        :return:
        res[0]：root为根的二叉树是否为BST，若为1，则是BST；若为0，则不是BST
        res[1]: 记录以root为根的二叉树所有节点的最小值
        res[2]: 记录以root为根的二叉树所有节点的最大值
        res[3]: 记录以root为根的二叉树所有节点值之和
        """
        # base case
        if not root:
            return [1, float('inf'), float('-inf'), 0]

        # 递归计算左右子树
        left = self.findMaxMinSum(root.left)
        right = self.findMaxMinSum(root.right)
        res = [None] * 4

        if left[0] == 1 and left[2] < root.val and right[0] == 1 and right[1] > root.val:
            res[0]= 1
            # 更新以root为根的这棵BST的最小值
            res[1] = min(left[1], root.val)
            # 更新以root为根的这棵BST的最大值
            res[2] = max(right[2], root.val)

            res[3] = left[3] + right[3] + root.val
            # 更新全局变量
            self.maxSum = max(self.maxSum, res[3])
        else:
            res[0] = 0
        #     其他值没必要计算了，用不到

        return res


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