LeetCode 第 1373 题：二叉搜索子树的最大键值和

LeetCode 第 1373 题：二叉搜索子树的最大键值和

题目 1373. 二叉搜索子树的最大键值和 的要求是，给你一颗以 root 为根的二叉树，要求返回任意二叉搜索子树的最大键值和。

首先要注意的是，给定的二叉树不一定是一颗二叉搜索树，所以我们要判断以某个节点为根节点的子树是否为二叉搜索树。

二叉搜索树的定义如下：

• 任意节点的左子树中的键值都 小于 此节点的键值。

• 任意节点的右子树中的键值都 大于 此节点的键值。

• 任意节点的左子树和右子树都是二叉搜索树。

暴力法

首先用比较暴力的解法，我们可以从根节点开始，判断以当前节点为根节点的二叉树是否为二叉搜索树（BST），如果是的话就计算这棵 BST 的键值和，然后更新最大键值和。可以给出如下代码：

class Solution:
    from collections import defaultdict
    def __init__(self):
        self.maxKeySum = 0  # 记录最大的 BST 键值和
        self.hashMap = defaultdict(int)  # 用一个哈希表来记录以当前节点为根节点的子树键值和

    def keySum(self, root):
        if not root: return 0
        leftVal = self.keySum(root.left)   # 得到左子树的键值和
        rightVal = self.keySum(root.right) # 得到右子树的键值和
        self.hashMap[root] = root.val + leftVal + rightVal
        return self.hashMap[root]  # 返回当前节点为根的树的键值和

    def findMax(self, root):  # 寻找最大的 BST 键值和
        if not root: return
        # 前序遍历
        # 如果 root 为 BST 并且其键值和大于当前最大键值和，就更新值
        if self.isBST(root) and (self.hashMap[root] > self.maxKeySum):
            self.maxKeySum = self.hashMap[root]
        self.maxSumBST(root.left) 
        self.maxSumBST(root.right) 

    def isBST(self, root, minNode=None, maxNode=None): # 验证是否为 BST
        if (root == None): return True
        if (minNode and root.val <= minNode.val): return False
        if (maxNode and root.val >= maxNode.val): return False
        return self.isBST(root.left, minNode, root) and self.isBST(root.right, root, maxNode)

    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        # 要判断以当前节点为根节点的树是否为二叉搜索树
        # 如果是的话更新最大键值和
        # 用前序
        self.keySum(root)  # 先创建键值和哈希表
        self.findMax(root) # 找到最大键值和
        return self.maxKeySum # 返回最大键值和

这个方法是能够对的，但是由于其时间复杂度太高，所以肯定是超时了。主要的原因在于每次调用函数 isBST(root) 的时候，都会重复遍历子节点。

后序遍历

在判断是否为 BST 的时候，可以使用后序遍历来记录 root 的左右子树是否为 BST 并且返回 root 树的最大和最小值，以及 root 的键值和。或者说，就是把上面的代码所有的函数都写成后序遍历的形式然后合并一下，得到下面的代码：

class Solution:
    from collections import defaultdict
    def __init__(self):
        self.maxKeySum = 0

    def traverse(self, root):
        if not root: return (True, float('-inf'), float('inf'), 0)
        leftIsBST, lMax, lMin, leftVal = self.traverse(root.left)
        rightIsBST, rMax, rMin, rightVal = self.traverse(root.right)
        # 后序遍历位置
        rootIsBST = leftIsBST and rightIsBST and (root.val > lMax) and (root.val < rMin)
        rootKeySum = root.val + leftVal + rightVal
        rootMax = max(lMax, rMax, root.val)
        rootMin = min(lMin, rMin, root.val)
        # 如果 root 是 BST 则更新最大键值和
        if rootIsBST:
            self.maxKeySum = max(self.maxKeySum, rootKeySum)
        # 返回 root 是否为 BST，最大值，最小值，键值和
        return (rootIsBST, rootMax, rootMin, rootKeySum)

    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        # 要判断以当前节点为根节点的树是否为二叉搜索树
        # 如果是的话更新最大键值和
        self.traverse(root)
        return self.maxKeySum

提供一个判断一棵树是否为 BST 的代码框架：

def isValidBST(root):
    return isValid(root, None, None)

# 让 root 的信息能够传给子树节点
def isValid(root, minNode, maxNode):
    if (root == None): return True
    if (minNode and root.val <= minNode.val): return False
    if (maxNode and root.val >= maxNode.val): return False
    # 左子树最大的值不能超过 root 节点
    # 右子树最小的值不能超过 root 节点
    return isValid(root.left, minNode, root) and isValid(root.right, root, maxNode)

参考：labuladong 的算法小抄