LeetCode 333. 最大二叉搜索子树

2021-08-14 HGNULB 约 11 分钟

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

分类

题目描述

✅ 333. 最大二叉搜索子树

题意分析

在一棵二叉树里找节点数最多的那棵「二叉搜索子树」，返回它的节点个数。这里的子树必须是完整子树：选定某个节点后，它的全部后代都必须一起被包含进来，不能只取其中一部分。

「必须是完整子树」这个限定非常重要，它意味着候选只有 n 个（每个节点各对应一棵子树），而不是指数级的任意连通块。于是问题变成「对每个节点判断它的子树是不是二叉搜索树，是的话规模多大」。

二叉搜索树的判定不是局部的：仅仅「左孩子比自己小、右孩子比自己大」远远不够，必须整棵左子树的所有值都小于根、整棵右子树的所有值都大于根。所以判定需要的信息量比「看一眼孩子」更多——至少要知道子树的取值范围。

节点数可达 10^4，取值范围是完整 int。取值跨满 int 意味着用来表示「空子树的极值」的哨兵不能取 Integer.MIN_VALUE/MAX_VALUE 后再参与比较，否则会和真实节点值撞上；要么把类型提升到 64 位，要么把空子树单独判掉。

边界包括：空树答案为 0；单节点树答案为 1；整棵树本身就是二叉搜索树时答案是 n；以及最大的合法子树深埋在一棵非法的大树内部的情况。

解法：后序遍历 + 子树信息合并

核心思路

暴力做法是对每个节点各跑一次「验证整棵子树是不是二叉搜索树」的遍历，再取通过验证的最大规模。这在链状树上是 $O(n^2)$，瓶颈在于父节点的验证过程会把孩子的整棵子树重新走一遍，而孩子刚刚才走过。

观察点是：判断「以 node 为根的子树是不是二叉搜索树」所需的全部信息，可以由两个孩子的同类信息一步合成，不需要再下探。具体地，只要知道左右子树各自「是不是 BST、有多少节点、最小值、最大值」，就能判定当前子树：左右都是 BST，且 left.max < node.val < right.min。

于是采用后序遍历，让每个节点向父亲返回一个四元组 (isBst, size, min, max)。返回值的语义必须一次定死，这里定为：

当 isBst 为真时，size 是这棵子树的节点数，min、max 是这棵子树的最小值和最大值；当 isBst 为假时，size 退化为「这棵子树内部所能找到的最大 BST 子树的节点数」，而 min、max 已无意义、不再被使用。

这个语义切换是本解法最微妙的地方，也是它能只用一次遍历就同时完成「判定」和「求最大」两件事的原因：合法时向上传递自己的完整刻画，非法时向上传递已经找到的最好答案。父节点在发现自己非法时，只需在两个孩子的 size 中取较大者继续上传，信息不会丢失。

不变量表述为：dfs(node) 返回后，若 isBst 为真则 size 恰为该子树节点数且 [min, max] 是其值域；若为假，则 size 恰为该子树内部最大 BST 子树的节点数。根据这条不变量，根节点返回的 size 就是全局答案——无论根本身是否合法。

空节点返回 (true, 0, +∞, -∞)。这组值是刻意设计的：把 min 设为正无穷、max 设为负无穷，可以让 node.val > left.max 和 node.val < right.min 在孩子为空时自动成立，从而消掉所有「孩子是否为空」的特判。为了让这两个哨兵不与真实节点值冲突，字段类型要提升到 64 位，或使用超出 int 值域的边界值。

解题步骤

定义一个承载四元组的小结构体 Info，字段为 isBst、size、min、max。之所以要打包成一个对象而不是用多个全局变量，是因为递归的每一层都需要独立的一份，全局变量会被兄弟子树互相覆盖。

空节点返回 (true, 0, 正无穷, 负无穷)。之所以 min 取正无穷而 max 取负无穷（看起来是反的），是因为空集的最小值应当大于一切、最大值应当小于一切，这样它在与父节点比较时永远不会构成阻碍。

先递归左孩子再递归右孩子，拿到两份 Info。之所以必须先递归后判断（即后序），是因为当前节点的合法性完全依赖孩子的结论，前序或中序拿不到这些信息。

判断 left.isBst && right.isBst && node.val > left.max && node.val < right.min。之所以四个条件缺一不可：前两个保证子树内部没有违规，后两个保证当前节点与两侧的全部取值都满足序关系——只比孩子的值是不够的，必须比子树的极值。

合法时返回 (true, left.size + right.size + 1, min(left.min, node.val), max(right.max, node.val))。之所以新的最小值取 left.min 与 node.val 的较小者，是因为左子树可能为空（此时 left.min 是正无穷，应当由 node.val 顶上）；最大值同理。

非法时返回 (false, max(left.size, right.size), 0, 0)。之所以 size 取两侧较大者，是因为按不变量两个孩子的 size 都已是各自子树内的最优答案，当前节点无法把它们合并成更大的 BST，只能择优上传；极值字段填任意值都行，因为 isBst 为假时父节点根本不会读它们。

最终返回根节点 Info 的 size。

以这棵树走一遍：根为 10，左孩子为 5，右孩子为 15；5 的左右孩子分别是 1 和 8；15 的右孩子是 7。预期答案是 3——以 5 为根的子树 {1, 5, 8} 是合法 BST，而以 15 为根的子树因为右孩子 7 小于 15 而非法，整棵树也因此非法。

从叶子开始。节点 1：两个孩子都空，left = (true, 0, +∞, -∞)，right 同；判断 1 > -∞ 且 1 < +∞ 成立，返回 (true, 1, min(+∞, 1) = 1, max(-∞, 1) = 1)。节点 8 同理返回 (true, 1, 8, 8)。

节点 5：左是 (true, 1, 1, 1)，右是 (true, 1, 8, 8)；判断 5 > 1 且 5 < 8 成立，返回 (true, 3, min(1, 5) = 1, max(8, 5) = 8)。

节点 7：叶子，返回 (true, 1, 7, 7)。

节点 15：左空为 (true, 0, +∞, -∞)，右是 (true, 1, 7, 7)；判断 15 > -∞ 成立，但 15 < 7 不成立，整体为假；返回 (false, max(0, 1) = 1, 0, 0)。这里 size = 1 的含义正是「15 的子树内部最大的 BST 有 1 个节点」，即节点 7 自己。

节点 10（根）：左是 (true, 3, 1, 8)，右是 (false, 1, 0, 0)；right.isBst 为假，整体为假；返回 (false, max(3, 1) = 3, 0, 0)。

最终返回 3，与预期一致。注意根节点虽然非法，size 字段仍然正确地携带了答案，这正是双语义设计的价值。

代码实现

class Solution {
    public int largestBSTSubtree(TreeNode root) {
        return dfs(root).size;
    }

    private Info dfs(TreeNode node) {
        if (node == null) {
            return new Info(true, 0, Long.MAX_VALUE, Long.MIN_VALUE);
        }

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

        if (left.isBst && right.isBst && node.val > left.max && node.val < right.min) {
            long min = Math.min(left.min, node.val);
            long max = Math.max(right.max, node.val);
            return new Info(true, left.size + right.size + 1, min, max);
        }

        int best = Math.max(left.size, right.size);
        return new Info(false, best, 0, 0);
    }

    private static class Info {
        boolean isBst;
        int size;
        long min;
        long max;

        Info(boolean isBst, int size, long min, long max) {
            this.isBst = isBst;
            this.size = size;
            this.min = min;
            this.max = max;
        }
    }
}

func largestBSTSubtree(root *TreeNode) int {
    return dfsLargest(root).size
}

type bstInfo struct {
    isBst bool
    size  int
    min   int
    max   int
}

func dfsLargest(node *TreeNode) bstInfo {
    if node == nil {
        return bstInfo{isBst: true, size: 0, min: maxInt(), max: minInt()}
    }

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

    if left.isBst && right.isBst && node.Val > left.max && node.Val < right.min {
        minVal := left.min
        if node.Val < minVal {
            minVal = node.Val
        }

        maxVal := right.max
        if node.Val > maxVal {
            maxVal = node.Val
        }

        return bstInfo{isBst: true, size: left.size + right.size + 1, min: minVal, max: maxVal}
    }

    best := left.size
    if right.size > best {
        best = right.size
    }

    return bstInfo{isBst: false, size: best, min: 0, max: 0}
}

func maxInt() int {
    return int(^uint(0) >> 1)
}

func minInt() int {
    return -maxInt() - 1
}

复杂度分析

时间复杂度：$O(n)$，凭据是每个节点恰好被 dfs 进入一次，节点内部只做常数次比较、取极值和一次对象构造，没有任何对子树的二次遍历。

空间复杂度：$O(h)$，其中 $h$ 是树高，凭据是每层递归只持有常数大小的 Info，栈深等于当前路径长度；平衡树为 $O(\log n)$，退化成链状树时为 $O(n)$。

关键点总结

「对每个子树都要判定一遍」的树上问题，标准解法是后序遍历一次，让每个节点向上返回一个能被父节点 $O(1)$ 合并的信息包，把 $O(n^2)$ 的重复下探压成 $O(n)$。

设计信息包的原则是「父节点做判断需要什么，就返回什么」。本题父节点需要子树的合法性和值域边界，所以四元组一个都不能少；只返回布尔值会导致父节点无法判断跨层的序关系。

允许返回值在不同情形下承载不同语义（合法时是自身刻画、非法时是内部最优解），可以省掉一个全局变量，但前提是把语义写在注释或脑子里并全程遵守——这也是这类题最容易出错的地方。

空子树的哨兵要设计成「永远不构成阻碍」：最小值取正无穷、最大值取负无穷，这样父节点的比较自动成立，所有空判特判都被消掉。

哨兵必须落在真实值域之外，值域跨满 int 时就要把字段提升到 64 位，否则真实节点取到 Integer.MIN_VALUE 时会与哨兵混淆。

面试视角：面试官会先问「怎么判断一棵树是不是 BST」（即 98 题），再加上「找最大的那棵合法子树」。答题时要主动指出朴素做法的重复遍历问题，然后提出「一次后序、每层返回信息包」的框架，并显式说明返回值在两种情形下的含义。常见追问是「如果要求的是键值和最大而不是节点数最多（1373 题）怎么改」，答案是把 size 换成 sum 并允许答案为负时取 0。

易错点总结

判定只比较孩子的值，写成 node.val > node.left.val && node.val < node.right.val：用例根为 10、左孩子为 5、5 的右孩子为 20 的树，10 > 5 成立但左子树里藏着 20，会把整棵树误判为 BST，返回 3 而非 2。

非法时返回 size = 0：用例根为 10、右孩子为 15、15 的右孩子为 7 的树，节点 15 非法后把 size 清零，根节点再取 max(左, 0)，会丢掉右子树内部找到的答案，在左子树也非法时直接返回 0。

空节点的 min、max 写反成 (true, 0, -∞, +∞)：用例任意单节点树，node.val > left.max 变成 node.val > +∞ 恒为假，所有节点都被判非法，返回 0。

空节点返回 isBst = false：用例单节点树 [5]，叶子的两个空孩子都不是 BST，叶子自身被判非法，返回 0 而非 1。

用 Integer.MIN_VALUE 作哨兵且字段类型是 int：用例根节点值恰为 -2147483648 的单节点树，node.val > left.max 变成 -2147483648 > -2147483648 为假，合法子树被误判为非法。

合法时新的 min 直接取 left.min 而不与 node.val 取小：用例单节点树 [5]，左子树为空时 left.min 是正无穷，向上传递的 min 就成了正无穷，父节点比较 node.val < right.min 时会误判成立，把非法结构当成 BST。

合法时 size 写成 max(left.size, right.size) + 1：用例三节点的完整 BST（1、5、8），返回 2 而非 3，规模统计漏掉了另一侧。

用一个全局变量记录最大值、同时让递归返回布尔值：用例根为 10、右孩子为 15、15 的右孩子为 7 的树，仅凭布尔值父节点无法知道该在哪个子树里取最优，还得额外再传规模，等于把四元组拆散后又要补回来，容易在某条分支上漏更新全局值。

先算判定再递归孩子（前序写法）：用例任意深度大于 2 的树，判定时 left、right 尚未求出，只能用默认值，结论恒错。

Go 里把 min/max 字段声明成 int 并用 math.MaxInt32：用例节点值为 2147483647 的树，node.Val < right.min 在右子树为空时变成 2147483647 < 2147483647 为假，合法叶子被误判；用平台位宽的 maxInt()/minInt() 才能保证哨兵严格在 int32 值域之外。

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	只判定整棵树，可自顶向下传上下界，无需向上返回信息包
1373. 二叉搜索子树的最大键值和	困难	目标换成键值和，需处理负数子树使答案可以为 0
110. 平衡二叉树	简单	同样的后序信息合并，返回高度并用 -1 编码「已失衡」的短路信号
543. 二叉树的直径	简单	返回值只上传单侧深度，答案取两侧之和，考察返回值与答案的分离
124. 二叉树中的最大路径和	困难	合并时要对负贡献截断，返回值语义与全局答案语义差异更大