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)
