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

2024-03-27 HGNULB 约 12 分钟

文章信息 7 个分类 6 个标签

分类

LeetCode CodeTop 困难未解决 2-5 字节跳动美团

题目描述

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

题意分析

给一棵二叉树，在它的所有子树中找出那些本身是二叉搜索树的，返回这些 BST 子树里键值和最大的那个和。

先把「子树」的定义钉死：这里的子树指的是以某个节点为根、连同它下面所有后代构成的整棵结构，不是任意挑几个节点组成的连通块。所以候选集合的大小恰好等于节点数，每个节点对应一个候选。

BST 的判定是严格的：左子树中所有节点的值都小于根，右子树中所有节点的值都大于根，且左右子树本身也都是 BST。注意是「所有节点」而不是「直接孩子」，这是这道题被评为困难而不是简单的唯一原因——只比较父子三元组会漏掉隔代违规的情况。

约束里有两条关键信息。节点数最多 $4 \times 10^4$，说明 $O(n^2)$ 的做法（对每个节点独立判一次 BST）在最坏的链状树上会退化到 $1.6 \times 10^9$ 次操作，风险很大，题目期待的是 $O(n)$。节点值范围是 $[-4 \times 10^4, 4 \times 10^4]$，可以为负，这直接影响答案的初值和「和越大越好」这个直觉。

边界有两处需要单独想。第一，单个节点永远是合法的 BST（空的左右子树自动满足条件），所以「不存在 BST 子树」这种情况其实不可能发生。第二，既然值可以为负，整棵树全是负数时所有 BST 子树的和都是负的；题目要求这种情况返回 0，也就是允许「一个都不选」。这两点合起来决定了答案变量的初值必须是 0 而不是负无穷。

解法：后序 DFS 汇总子树信息

核心思路

暴力做法很自然：枚举每个节点，对以它为根的子树跑一次完整的 BST 校验并求和，取所有合法子树里的最大值。校验和求和各是 $O(size)$，累计起来在链状树上是 $O(n^2)$。瓶颈同样明显——同一棵子树被反复遍历了无数次，每个祖先都要把它重新走一遍。

关键观察是：判断一棵子树是不是 BST，只需要它两个孩子子树的四项汇总信息，不需要重新遍历。具体地，以 node 为根的子树是 BST 当且仅当同时满足四条：左子树是 BST、右子树是 BST、node.val 严格大于左子树中的最大值、node.val 严格小于右子树中的最小值。第三、四条正是把「所有后代都合规」这个全局条件压缩成了两个数——只要压住了左边的最大值和右边的最小值，隔代违规就无处藏身。

于是把它写成树形 DP。定义 dfs(node) 返回一个四元组 (isBST, min, max, sum)：isBST 表示以 node 为根的子树是否为 BST；min / max 是该子树中的最小 / 最大键值；sum 是该子树所有键值之和。约定当 isBST 为假时，后三个字段无意义、不会被父层读取（因为父层第一个条件就短路了）。这个「返回值语义前后一致」的约定是树形 DP 能写对的前提。

空节点返回 (true, +∞, -∞, 0)。这组哨兵不是随便挑的，它的作用是让叶子节点无需任何特判就走通主逻辑：叶子的左孩子返回 max = -∞，于是 node.val > left.max 恒成立；右孩子返回 min = +∞，于是 node.val < right.min 恒成立；接着 min = min(left.min, node.val) = min(+∞, node.val) = node.val，max = max(right.max, node.val) = max(-∞, node.val) = node.val，sum = 0 + 0 + node.val，全部正确。用 0 当哨兵会立刻破坏这一切。

合并时 min 只需要 min(left.min, node.val)、max 只需要 max(right.max, node.val)，不用把左右两边都取一遍。原因是：走到这一步说明已经确认了是 BST，那么右子树的所有值都大于 node.val，不可能提供更小的最小值；对称地左子树也不可能提供更大的最大值。写成对左右都取 min/max 也不会错，只是多余。

答案的更新时机是「每当确认一棵子树是 BST 就用它的 sum 去更新全局最大值」。答案变量是一个跨递归层的全局量，而 dfs 的返回值是纯粹的局部信息，两者语义必须分开——这是树形 DP 里「全局答案 + 局部返回」这一对搭档的标准分工，和 124 题最大路径和是同一个模式。答案初值取 0，正好把「全负树返回 0」这条要求实现掉。

解题步骤

确定递归返回值的语义并写死：(isBST, min, max, sum)，其中后三项仅在 isBST 为真时有效。写代码之前先把这句话说清楚，后面所有分支都围绕它展开；语义模糊是树形 DP 写不对的头号原因。

处理空节点：返回 (true, +∞, -∞, 0)。空子树视为合法 BST 是必须的，否则任何叶子都会因为孩子不合法而被判否，整棵树一个 BST 都找不到。哨兵取反向极值是为了让边界比较自动通过。

先递归左右孩子，再做当前节点的判断：这是后序遍历。顺序不能反——当前节点的合法性完全依赖孩子的汇总信息，先序或中序拿不到这些信息。

四条件合取判断：left.isBST && right.isBST && node.val > left.max && node.val < right.min。两个比较都必须是严格不等号，因为 BST 不允许重复键值；写成 >= 或 <= 会把含重复值的非法子树判成合法。

合法分支：算和、更新答案、上传新的四元组：sum = left.sum + right.sum + node.val，用它更新全局答案，然后返回 (true, min(left.min, node.val), max(right.max, node.val), sum)。

非法分支：返回 isBST = false，其余字段随意：只要保证父层看到 false 就短路即可。这一步还有个隐含的重要含义——一旦某个节点不是 BST，它的所有祖先都不可能是 BST，因为 BST 要求左右子树本身合法。所以这个 false 会一路向上传染，正确地把整条祖先链排除掉。

返回全局答案：注意返回的不是 dfs(root) 的 sum。根节点自己可能根本不是 BST，答案往往藏在某棵子树里。

以下面这棵树走一遍：

dfs(1)：左右孩子都是空，各返回 (true, +∞, -∞, 0)。判断 true && true && 1 > -∞ && 1 < +∞，四条全过。sum = 0 + 0 + 1 = 1，答案从 0 更新为 1。上传 (true, min(+∞,1)=1, max(-∞,1)=1, 1)。

dfs(2)：同理上传 (true, 2, 2, 2)，答案从 1 更新为 2。

dfs(3)：left = (true, 1, 1, 1)，right = (true, 2, 2, 2)。判断 left.isBST 过、right.isBST 过、3 > left.max = 1 过，但 3 < right.min = 2 不成立——右子树里的 2 比根 3 还小，违反 BST。返回 (false, ...)，答案不更新。

dfs(4)：left = (false, ...)，第一个条件就短路，返回 (false, ...)，答案仍不更新。

最终答案是 2，也就是只含节点 2 的那棵单节点子树。可以人工核对：候选有 {4,3,1,2}（不是 BST）、{3,1,2}（不是）、{1}（是，和 1）、{2}（是，和 2），最大确实是 2。

再看一个专门打「只比父子」错误写法的例子：

如果只比较每个节点与它的直接孩子，10 > 5、10 < 15、15 > 6、15 < 20 全都成立，整棵树会被误判成 BST。但节点 6 在根 10 的右子树里却小于 10，是非法的。用本题的边界法：dfs(15) 的左子树 {6} 上传 min = max = 6，15 > 6 通过，15 < 20 通过，{15,6,20} 确实是合法 BST（和 41），继续上传 min = min(6, 15) = 6。到 dfs(10) 时检查 10 < right.min = 6 失败，正确地判定整棵树不是 BST。最终答案是 {15,6,20} 的 41。这一步正是「上传 min/max」相对「只看父子」的全部价值。

代码实现

class Solution {
    private int answer;

    public int maxSumBST(TreeNode root) {
        // 节点值可以为负，题目要求全负时返回 0，所以初值取 0 而非负无穷。
        answer = 0;
        dfs(root);
        return answer;
    }

    private Info dfs(TreeNode node) {
        if (node == null) {
            // 反向极值哨兵：让叶子节点的两个边界比较自动通过，无需特判。
            return new Info(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }

        Info left = dfs(node.left);
        Info right = dfs(node.right);

        // 严格不等号：BST 不允许重复键值。压住左边最大、右边最小即可覆盖全部后代。
        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);
            // 已确认是 BST，右子树全大于 node.val，故最小值只可能来自左边，反之亦然。
            int min = Math.min(left.min, node.val);
            int max = Math.max(right.max, node.val);
            return new Info(true, min, max, sum);
        }

        // 非法时后三个字段不会被父层读取，父层第一个条件就会短路。
        return new Info(false, 0, 0, 0);
    }

    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 {
    // 节点值可以为负，题目要求全负时返回 0，所以初值取 0 而非负无穷。
    answer := 0
    var dfs func(*TreeNode) info

    dfs = func(node *TreeNode) info {
        if node == nil {
            // 反向极值哨兵：让叶子节点的两个边界比较自动通过，无需特判。
            return info{isBST: true, min: 1 << 30, max: -1 << 30}
        }

        left := dfs(node.Left)
        right := dfs(node.Right)

        // 严格不等号：BST 不允许重复键值。压住左边最大、右边最小即可覆盖全部后代。
        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
            }
            // 已确认是 BST，右子树全大于 node.Val，故最小值只可能来自左边，反之亦然。
            minVal := left.min
            if node.Val < minVal {
                minVal = node.Val
            }
            maxVal := right.max
            if node.Val > maxVal {
                maxVal = node.Val
            }
            return info{isBST: true, min: minVal, max: maxVal, sum: sum}
        }

        // 零值的 isBST 恰好是 false，父层会在第一个条件短路。
        return info{}
    }

    dfs(root)
    return answer
}

复杂度分析

时间复杂度：$O(n)$，$n$ 为节点数。每个节点在后序遍历中被访问且只被访问一次，访问时做的是四次比较、两次取极值、一次加法，全是常数操作；子树信息靠上传复用，没有任何重复遍历。相比暴力的 $O(n^2)$，省下的正是「对每棵子树重新校验」的那一层。

空间复杂度：$O(h)$，$h$ 为树高，来自递归调用栈；每层只存一个常数大小的四元组。平衡树时是 $O(\log n)$，退化成链时是 $O(n)$，最坏情况下 $4 \times 10^4$ 层的递归在 JVM 默认栈上仍是安全的。

关键点总结

「判断子树整体性质」类问题的通用解法是后序 DFS 上传汇总信息：把「所有后代都满足某条件」压缩成常数个可合并的统计量（这里是 min、max、isBST、sum），从而把 $O(n^2)$ 降到 $O(n)$。这个套路能直接迁移到 98、333、110 等一大票题。

递归返回值必须有一句能写在纸上的、前后一致的语义，并明确「什么时候哪些字段有效」。语义漂移是树形 DP 最常见的失败模式，比任何具体的边界错误都致命。

空节点的哨兵要选反向极值（min 取 $+\infty$、max 取 $-\infty$），这样叶子节点的边界比较自动成立，可以省掉叶子特判。凡是「用哨兵消灭特判」的地方，都要能说清哨兵为什么是那个方向。

全局答案与递归返回值是两个不同的东西：返回值描述局部子树，全局答案跨层累积。124、543、687 等题用的都是这一对搭档，混用语义会立刻出错。

答案初值要由题目对「无解」的定义倒推。本题因为值可为负且要求全负时返回 0，初值必须是 0；如果题目改成「必须选一棵」，初值就得是负无穷。面试里主动区分这两种情形是加分项。

非法结果向上传染是这个解法的正确性支柱：某节点不是 BST，其所有祖先必然也不是。理解这一点就能明白为什么非法分支不需要携带任何有效数据。

易错点总结

只比较节点与直接孩子的值：上面 [10,5,15,null,null,6,20] 那棵树会被误判为 BST，输出 56，而正确答案是 41。这是本题最经典、也最难自查的错误。

边界比较写成 node.val >= left.max 或 node.val <= right.min：[2,2,2] 这种含重复值的树会被判成 BST，输出 6，正确答案是 2（单节点）。

答案初值写成 Integer.MIN_VALUE：树全是负数时（如 [-4,-2,-5]）会返回 -2，而题目要求返回 0。

空节点返回 (true, 0, 0, 0)：哨兵方向错了。对负值节点如 -5，判断 -5 > left.max = 0 直接失败，明明合法的单节点子树被漏掉，答案系统性偏小。

合并时写成 min = Math.min(left.min, right.min)，漏掉 node.val：对单节点子树，left.min 和 right.min 都是 $+\infty$ 哨兵，上传的 min 仍是 $+\infty$，父层的 node.val < right.min 会永远成立，隔代违规又被放行。

最后返回 dfs(root).sum：根不是 BST 时这个字段是非法分支填的 0（或垃圾值），会丢掉藏在子树里的真答案。上面 [10,5,15,null,null,6,20] 会返回 0 而不是 41。

在合法分支里忘记更新全局答案，只在根节点更新：只有整棵树是 BST 时才有输出，其余情况一律返回 0。

写成先序：先判断当前节点再递归孩子：此时孩子的 min/max/sum 还没算出来，判断条件读到的是未初始化的值，逻辑整个不成立。

sum 忘记加 node.val，只加了左右子树的和：所有 BST 子树的和都少一个根值，单节点子树的和全变成 0，答案偏小。

Go 里非法分支返回 info{isBST: true}：零值忘了保持 isBST 为 false，会把所有非法子树当成合法的空树，min/max 又是 0，结果完全错乱。

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	只判整棵树是否 BST，本题的判定部分；也可用中序遍历递增性替代边界上传
333. 最大二叉搜索子树	中等	求最大 BST 子树的节点数而非键值和，四元组把 sum 换成 size 即可
124. 二叉树中的最大路径和	困难	同为「全局答案 + 局部返回」，但路径可在节点处拐弯，上传的是单边链和
543. 二叉树的直径	简单	后序上传深度、在每个节点合并更新全局答案，是这套模式最精简的形态
110. 平衡二叉树	简单	上传「高度 + 是否平衡」，与本题的「边界 + 是否 BST」结构完全同构
337. 打家劫舍 III	中等	每个节点上传选与不选两个状态值，是树形 DP 的另一条主线
1339. 分裂二叉树的最大乘积	中等	后序上传子树和后再枚举断哪条边，用到本题四元组里的 sum 分量