LeetCode 1373. 二叉搜索子树的最大键值和
题目描述
题意分析
从某个节点及其全部后代组成的完整子树中，寻找键值和最大的二叉搜索树。BST 要求所有左侧后代严格小于根、所有右侧后代严格大于根，不能任意删掉不合适的节点。题目允许选择空树，因此全负时答案为 0。
解法：迭代后序汇总子树信息
核心思路
[!blue]
判断当前节点能否作为 BST 的根，需要知道左右子树各自是否合法，以及所有后代的值域，而不是只比较两个直接孩子。因此为每棵子树保存四项信息：
isBST、最小值min、最大值max和完整键值和sum。当前子树合法，当且仅当左右子树都是 BST，并且
left.max < node.val < right.min。左侧最大值都小于根，就保证左侧所有后代都小于根；右侧同理。合法时，总和是两侧总和加根值，最小值来自左子树或根，最大值来自右子树或根，由此合成当前节点的汇总。若任一条件失败，就只上传
isBST = false，父节点不能再把整棵子树当作 BST。其内部已经找到的合法子树仍保留在answer中，不会因父层失败而丢失。每个合法根都用自己的完整sum更新答案；即使某个孩子的和为负，也必须计入，不能像求可选路径那样将它截成 0。空子树视为合法，总和为 0，最小值设为大于所有节点值的哨兵，最大值设为小于所有节点值的哨兵。这样缺少某侧孩子时，范围条件自然成立，叶子也无需额外分支。
answer从 0 开始，代表允许选择空树。为先得到孩子信息，代码把节点收集到父在子前的
order列表，再倒序计算；倒序后每个孩子都早于父节点，已经具备自底向上的依赖顺序。结果按节点对象或指针保存在summaries，不能按可能重复的键值保存。该方法不用递归调用栈，也能处理退化成链的深树。
解题步骤
- 从根开始收集节点，循环持续访问新追加的孩子。
- 倒序遍历列表，读取左右孩子的汇总。
- 按严格边界合成当前汇总，合法时更新答案。
- 保存当前节点结果，最后返回本次调用的最大和。
代码实现
class Solution {
public int maxSumBST(TreeNode root) {
List<TreeNode> order = new ArrayList<>();
if (root != null) {
order.add(root);
}
// 持续处理新追加的孩子，保证父节点总排在子节点之前。
for (int i = 0; i < order.size(); i++) {
TreeNode node = order.get(i);
if (node.left != null) {
order.add(node.left);
}
if (node.right != null) {
order.add(node.right);
}
}
// 按节点身份保存各子树汇总，不修改原树连接。
Map<TreeNode, Info> summaries = new IdentityHashMap<>();
Info empty = new Info(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
int answer = 0;
// 倒序处理时，非空孩子的汇总已经存在。
for (int i = order.size() - 1; i >= 0; i--) {
TreeNode node = order.get(i);
// 只有空孩子才使用合法空子树汇总，非空孩子读取已计算结果。
Info left = node.left == null ? empty : summaries.get(node.left);
Info right = node.right == null ? empty : summaries.get(node.right);
Info current;
// 先确认两侧合法，再用严格边界覆盖全部后代。
if (left.isBST && right.isBST && node.val > left.max && node.val < right.min) {
int sum = left.sum + right.sum + node.val;
answer = Math.max(answer, sum);
current =
new Info(
true,
Math.min(left.min, node.val),
Math.max(right.max, node.val),
sum);
} else {
// 非法子树只上传失败，父层不会使用其范围与总和。
current = new Info(false, 0, 0, 0);
}
summaries.put(node, current);
}
return answer;
}
private static class Info {
boolean isBST;
int min;
int max;
int sum;
Info(boolean isBST, int min, int max, int sum) {
this.isBST = isBST;
this.min = min;
this.max = max;
this.sum = sum;
}
}
}
type info struct {
isBST bool
min int
max int
sum int
}
func maxSumBST(root *TreeNode) int {
order := make([]*TreeNode, 0)
if root != nil {
order = append(order, root)
}
// 循环每次读取最新长度，不能用只固定初始长度的范围遍历。
for i := 0; i < len(order); i++ {
node := order[i]
if node.Left != nil {
order = append(order, node.Left)
}
if node.Right != nil {
order = append(order, node.Right)
}
}
// 按节点指针保存子树汇总，不修改原树连接。
summaries := make(map[*TreeNode]info, len(order))
empty := info{isBST: true, min: 1 << 30, max: -1 << 30}
answer := 0
// 倒序处理时，非空孩子的汇总已经存在。
for i := len(order) - 1; i >= 0; i-- {
node := order[i]
// 空孩子使用合法空汇总，非空孩子改读其已计算结果。
left := empty
if node.Left != nil {
left = summaries[node.Left]
}
right := empty
if node.Right != nil {
right = summaries[node.Right]
}
// 零值表示非法；只有完整通过两侧与严格边界检查才设置为合法。
current := info{}
// 先确认两侧合法，避免使用非法汇总中的范围与总和。
if left.isBST && right.isBST && node.Val > left.max && node.Val < right.min {
sum := left.sum + right.sum + node.Val
if sum > answer {
answer = sum
}
minVal := left.min
if node.Val < minVal {
minVal = node.Val
}
maxVal := right.max
if node.Val > maxVal {
maxVal = node.Val
}
current = info{isBST: true, min: minVal, max: maxVal, sum: sum}
}
summaries[node] = current
}
return answer
}
复杂度分析
- 时间复杂度：期望 $O(n)$，每个节点收集、汇总各一次，按节点查表平均为常数时间。
- 空间复杂度：$O(n)$，节点列表与子树汇总表。
关键点总结
[!green]
- min、max、sum 只在 isBST 为真时有意义。
- 全局答案独立于根子树是否合法。
- 收集节点时循环条件要读取列表的最新长度，追加的孩子也必须继续访问。
- 题面键值在 $[-4\times10^4,4\times10^4]$ 内，代码的两端哨兵严格位于该范围之外。
易错点总结
[!yellow]
- 只比较直接孩子，会漏掉更深后代违反根节点值域的情况。
- 允许等号会把重复键值接受为 BST。
- 直接返回根的子树和，会漏掉内部更优子树。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 333. 最大二叉搜索子树 | 中等 | 同样后序返回BST有效性与值域边界，原题最大化节点数量，本题最大化节点和。 |
| 98. 验证二叉搜索树 | 中等 | BST全局上下界条件是基础，本题还要对每个有效子树汇总数值并更新答案。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！