二叉搜索子树的最大键值和 -- 后序遍历的扩展应用

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

classMaxSumBST:"""
    后序遍历

    二叉搜索子树的最大键值和
    https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/
    """def__init__(self):
        self.maxSum =0defmaxSumBst(self, root: TreeNode):
        self.findMaxMinSum(root)return self.maxSum

    deffindMaxMinSum(self, root: TreeNode):"""

        :param root:
        :return:
        res[0]：root为根的二叉树是否为BST，若为1，则是BST；若为0，则不是BST
        res[1]: 记录以root为根的二叉树所有节点的最小值
        res[2]: 记录以root为根的二叉树所有节点的最大值
        res[1]: 记录以root为根的二叉树所有节点值之和
        """# base caseifnot root:return[1,float('inf'),float('-inf'),0]# 递归计算左右子树
        left = self.findMaxMinSum(root.left)
        right = self.findMaxMinSum(root.right)# 后序遍历，更新全局变量
        res =[None]*4if left[0]==1and left[2]< root.value and right[0]==1and right[1]> root.value:
            res[0]=1# 计算以root为根的这棵BST的最小值，这里之所以要和root节点比较取最值的原因是，叶子节点的左右子树分别返回# 无穷大值、无穷小值，会影响叶子节点的返回值
            res[1]=min(left[1], root.value)# 计算以root为根的这棵BST的最大值
            res[2]=max(right[2], root.value)# 计算以root为根的这棵BST所有节点之和
            res[3]= left[3]+ right[3]+ root.value
            # 更新全局变量
            self.maxSum =max(self.maxSum, res[3])else:
            res[0]=0#     其他值没必要计算了，用不到return res