LeetCode 333：最大BST子树问题与树形DP递归状态设计详解

刷LeetCode 333的人，十有八九会卡在递归返回值的设计上。题面很短：给一棵普通二叉树，在里面找出最大的二叉搜索子树，返回节点数。听起来不就是判断BST吗？真写起来才发现，判断一棵树是不是BST容易，找“最大BST子树”完全是另一回事。尤其这道题还被放进会员尊享面试100题里，面试官为了考察你对二叉树结构的理解、递归返回值的建模能力，经常把它当压轴题来用。

我刷这道题刷了三遍，第一遍稀里糊涂背代码，第二遍勉强理解，第三遍才真正想明白为什么要把min、max、size一起往上传。这篇文章不打算复述官方题解，而是按我实际踩坑和帮助别人排查问题的经验，把这道题从暴力思路到最终代码、再到面试延伸话题完整拆一遍，尤其是很多题解里不会仔细讲的边界条件和容易翻车的细节。

1. 这道题到底在考什么

1.1 题面拆解：最大二叉搜索子树是什么意思

先统一认知。所谓“子树”，在这类题里指的是以某个节点为根、包含它所有后代节点的完整结构。你不能从一棵BST子树里单独抠几个节点再拼出一个东西来，那叫子序列，不是子树。所以题目等价于：枚举树上所有“以节点为根”的子树，找出其中满足BST性质的，返回节点数最多的那个大小。

举个例子，一棵树root为10，左孩子为6，右孩子为15，右子树左孩子为7、右孩子为20。表面上每个局部都合法：10大于6小于15，15大于7小于20。但整棵树不是BST，因为7作为10右子树的一部分，必须大于10，7却不满足。真正最大的BST子树是右侧那棵[15, 7, 20]，节点数为3。

这个例子就是整道题的核心。如果你只会看相邻两层的大小关系，一定会误判。BST的约束是全局的，根节点需要限制整棵左子树的最大值、整棵右子树的最小值，而不是只看直接孩子。

1.2 为什么很多人一上来就写错递归

大多数人的第一反应是写一个判断BST的函数，然后对每个节点调用一次，再统计最大值。这个思路本身没错，但复杂度很高：最坏情况下每个节点都要向下扫描整棵子树，整体达到O(n²)。在面试现场，如果一开始写O(n²)版本，面试官通常不会直接否定你，而是会追问“能不能优化到O(n)”。

更麻烦的是，判断函数里你很难同时完成“统计节点数”和“向上层汇报信息”两件事。比如你用经典的中序遍历判断BST，判断到某个节点时确实能确定以它为根的子树是否合法，但你要怎么把它传给父节点？一个布尔值显然不够，父节点需要知道以当前节点为根的子树里的最小值、最大值、以及节点总数。信息不足，递归就没法继续组合。

所以这道题真正考察的，是你能不能设计出一个足够“厚”的递归返回对象，让每一层子树把需要的信息都汇总上传，让上层不用重新遍历就能做判断。

2. 别急着写递归：先把信息模型想透

2.1 自顶向下为什么别扭

有人会问，能不能在递归时把root.val作为参数传下去，从根开始检查每个节点是否在允许区间内？这是很自然的思路。比如判断一棵树是不是BST，就是从上往下维护一个 [lower, upper] 区间，左孩子用 [lower, root.val)，右孩子用 (root.val, upper]（严格小于时）。这个办法用来验证整棵树非常舒服。

但在“找最大BST子树”里，你面对的不是一棵确定的树，而是很多棵可能的子树。对于某个节点node，它只有在左子树整体合法、右子树整体合法、且左子树最大值小于node.val、右子树最小值大于node.val时，以node为根的子树才是BST。这些信息是典型的“由下往上推导”的信息，也就是树形DP。自上而下传区间只能做合法性验证，做不了尺寸聚合。

打个比方：你要统计一支队伍里最长的一段严格递增排列。如果从队伍头开始边走边看，你只能知道目前这段是否递增，却不知道后面某一段是否更长，因为你不知道后面一段的内部顺序。只有从队伍尾部往回整理，才能把“以某个人为终点/起点的最长递增段长度”汇总出来。

2.2 后序遍历：天然匹配“先子后父”的信息流

后序遍历的顺序是左子树、右子树、当前节点。这个顺序和我们的需求完美对应：要决策当前节点能不能作为BST的根，必须先知道左右子树内部的min和max是否和当前节点值兼容；要统计当前节点作为根的子树大小，必须先知道左右子树各自的大小。反之，前序或中序都不方便，因为它们要么在拿到子树信息之前就要决策，要么会把中间节点先处理掉，导致无法同时拿到左右两侧的汇总信息。

所以这道题的标准解法，就是递归函数对每个节点都返回四个信息：当前子树是不是BST、当前子树的节点总数、当前子树的最小值、当前子树的最大值。父节点只需要检查左右子树的四个信息，就能完成拼接判断。

2.3 递归返回对象：用代码把“信息流”具象化

在Java里，最直观的做法是定义一个内部类：

class Result { boolean isBST; // 以当前节点为根的整棵子树是否满足BST int size; // 以当前节点为根的子树节点总数 long min; // 当前子树中的最小值 long max; // 当前子树中的最大值 Result(boolean isBST, int size, long min, long max) { this.isBST = isBST; this.size = size; this.min = min; this.max = max; } }

为什么min和max要用long而不直接用int？这个很多人没注意。叶子节点或空子树需要返回一个“正负无穷”哨兵，方便父节点用小于/大于来比较。如果直接用Integer.MAX_VALUE和Integer.MIN_VALUE做哨兵，一旦某个节点的值恰好等于这两个边界值，就可能误判。我见过不只一个同学在这种边界上翻车，所以这里提前用long做哨兵，哪怕题目给的val都在int范围内，也绝对安全。

Result里的size表示的是“以当前节点为根的整棵子树的全部节点数”，而不是“当前子树里最大的BST大小”。这两个概念非常关键。如果你返回的是后者，上层节点就没法正确拼接：因为以当前节点为根的BST如果成立，就必须把当前节点左右子树的所有节点都包含进去，不能只取一部分。换句话说，这个Result描述的是“整棵子树本身的状态”，不是“子树内部的最优答案”。

3. 完整代码实现与逐步解读

3.1 核心代码：后序遍历 + 状态聚合

我用Java写一版完整实现，直接可用：

class Solution { private class Result { boolean isBST; int size; long min; long max; Result(boolean isBST, int size, long min, long max) { this.isBST = isBST; this.size = size; this.min = min; this.max = max; } } private int maxSize = 0; public int largestBSTSubtree(TreeNode root) { if (root == null) { return 0; } dfs(root); return maxSize; } private Result dfs(TreeNode node) { if (node == null) { // 空树按BST处理，节点数为0，min给正无穷，max给负无穷 return new Result(true, 0, Long.MAX_VALUE, Long.MIN_VALUE); } Result left = dfs(node.left); Result right = dfs(node.right); // 左子树或右子树不是BST，或者当前节点破坏BST顺序，均不合法 if (!left.isBST || !right.isBST || node.val <= left.max || node.val >= right.min) { // 返回一个isBST=false的结果，size和min/max不再有意义 return new Result(false, 0, 0, 0); } // 以node为根的整棵子树合法 int size = left.size + right.size + 1; long min = Math.min(node.val, left.min); long max = Math.max(node.val, right.max); maxSize = Math.max(maxSize, size); return new Result(true, size, min, max); } }

主方法里先判空，然后调用dfs。注意dfs的过程中会不断更新maxSize，所以最终直接返回这个全局变量即可。

3.2 一行一行拆解：空节点为什么这样设计

很多人不理解空节点为什么要返回new Result(true, 0, Long.MAX_VALUE, Long.MIN_VALUE)。这是整个递归的边界条件。

空树是BST，所以isBST为true，size为0。关键是min和max。对于空节点，它没有“最小值”和“最大值”，但父节点比较时要保证空子树不会干扰判断。把空节点的最小值设成正无穷、最大值设成负无穷，会让所有正常的节点值都比空节点的左max大、比空节点的右min小，从而自动通过比较。

比如node只有一个左孩子，没有右孩子。右子树的返回值是(min=Long.MAX_VALUE, max=Long.MIN_VALUE)。判断node.val >= right.min，即node.val >= Long.MAX_VALUE，必然为false，说明右子树不存在非法的最小值，判断通过。左子树同理：node.val <= left.max，如果left为空，left.max是Long.MIN_VALUE，必然为false，判断通过。于是单节点树就能正确返回size=1。

如果不用这种哨兵写法，就得频繁判断left == null、right == null，代码会变得很啰嗦，而且很容易漏判，比如只处理了左边空、忘了右边空。用哨兵把边界情况收进统一逻辑，是这类树形DP非常实用的技巧。

3.3 关键合并逻辑：为什么非法子树要先判断

代码里有一段容易被忽略的顺序问题：

if (!left.isBST || !right.isBST || node.val <= left.max || node.val >= right.min) { return new Result(false, 0, 0, 0); }

这个条件的顺序是刻意安排的。先看左右子树是不是BST，再看值的大小关系。Java的||有短路特性，如果left或right已经非法，后面的left.max和right.min根本不会被读取，这很重要。因为非法结果里的min和max被我随手写成了0，如果先去拿left.max做比较，就会拿脏数据去判断，得出一堆诡异结论。

如果你换成isBST=false时仍然保留真实的min和max，那顺序写反了也不会出错，但为了安全和简洁，我选择非法时直接让min和max失去意义。这样写能保证整个递归的状态流转非常干净：isBST=false的结果只负责阻断上层拼接，不参与任何大小比较。

3.4 用反例亲手推一遍递归过程

再看开头那个例子：[10, 6, 15, null, null, 7, 20]。

递归会先处理左子树[6]，返回Result(true, 1, 6, 6)。然后处理右子树[15, 7, 20]：

• 处理[20]，返回Result(true, 1, 20, 20)
• 处理[7]，返回Result(true, 1, 7, 7)
• 得到右子树根15的结果时，left是7这个节点（min=7, max=7），right是20这个节点（min=20, max=20），判断15 <= 7为false，15 >= 20为false，于是返回Result(true, 3, 7, 20)。

回到根节点10，此时left是[6]节点的Result(true, 1, 6, 6)，right是[15, 7, 20]的Result(true, 3, 7, 20)。判断条件里node.val <= left.max，即10 <= 6为false，没问题；但第二个条件node.val >= right.min，即10 >= 7为true，于是整体判定非法，返回Result(false, 0, 0, 0)。

虽然根节点不是BST，但right子树内部合法的结果已经在递归过程中通过maxSize记录下来了，最大值就是3。所以最终返回3。

这个手推过程每道题都值得做一遍。一旦你自己能把这个递归表画出来，就很难再写错。

4. 现场容易踩的坑和排查思路

4.1 只比较左右孩子值：最常见的翻车点

很多人写出的第一版本地运行也能过几个用例，但一到偏斜的测试就挂。核心原因是只比较了node和left、right的直接值。用前面那个反例，只比较10和6、10和15，完全正确；再比较15和7、15和20，也完全正确。于是返回整个树的size=5，正确答案却是3。

这类错误在LeetCode上不会报编译错误，只会显示Wrong Answer，而且不一定每个用例都错，排查起来很烦。建议遇到这类题目，先画一棵树，要求自己：“在判断某个节点之前，先问这棵子树里全局最小值和全局最大值是多少”。把这个思路写进代码里，就不会只盯着直接孩子看了。

4.2 把“子树内最优”当成“子树自身状态”返回

还有一种隐蔽的错误。有人理解了要返回size，但返回的不是以当前节点为根的整棵子树节点数，而是当前子树内部能找到的最大BST的size。

比如一棵子树自身不是BST，但它内部有一棵大小为100的BST子树。有人会想，那我把100返回给上一层，说不定父节点可以用它拼接出更大的结果。这是错的。因为父节点如果想以自己为根组成BST，就必须包含这棵子树的全部节点，不能跳过中间不符合BST的部分。BST是整棵子树的性质，不是几个节点拼凑出来的序列。

怎么自查？你可以把Result里的size字段理解成“证据”：isBST=true的size，必须是这棵子树“所有节点”的总数。如果是子树的部分节点数，就说明你还没把“子树自身状态”和“子树内部最优”这两个概念分开。

4.3 边界值：Integer哨兵和极端val导致的误判

有同学问我，为什么别人代码里用Integer.MAX_VALUE做哨兵，我的代码也用了，却在一个节点的val等于Integer.MAX_VALUE的单节点用例上报错。

原因就在前面说的：如果node.val是Integer.MAX_VALUE，且右子树为空，判断node.val >= right.min时，right.min正好也是Integer.MAX_VALUE，于是Integer.MAX_VALUE >= Integer.MAX_VALUE成立，当前节点被误判为非法。

解决思路有三种：

• 把min和max设成long，用Long.MAX_VALUE和Long.MIN_VALUE做哨兵；
• 在比较之前显式判断left.size == 0或right.size == 0，避免用空子树哨兵值做比较；
• 用带空判断的单独分支处理左右子树为空的情况。

最省心的是第一种。用long之后，int范围内的值永远碰不到long的极值，这个问题就消失了。面试时主动点出这个细节，面试官一般都会认可你是真的考虑过边界情况。

4.4 自测用例清单

我平时刷题不会只跑一遍示例就提交，这道题我至少会准备以下几组自测：

第4组用例就是[10, 6, 15, null, null, 7, 20]，期望输出是3。第6组可以构造一个val等于Integer.MIN_VALUE的单节点，或者val等于Integer.MAX_VALUE的单节点，确保代码不会误判成0。

4.5 重复值：严格小于还是小于等于

LeetCode 333默认按严格BST来理解：左子树所有节点值严格小于当前节点，右子树严格大于当前节点。代码里对应的判断是：

node.val <= left.max // 等于左子树最大值，视为不合法 node.val >= right.min // 等于右子树最小值，视为不合法

如果面试官改了定义，说允许重复值，也就是左子树可以小于等于当前节点，那只需要把这两个比较符号改成<和>即可。但要注意，一旦允许重复值，空哨兵和边界判断的思路不变，变的只有比较符号。面到这种细节时，最好主动和面试官确认定义，不要自己默默假设。

5. 同类变体和面试加分方向

5.1 变体一：要求返回最大BST子树本身

有些面试题会从“返回节点数”进一步改成“返回这个子树的根节点”。实现方式几乎不用改动，只需要在Result里多存一个TreeNode bestRoot。

合法状态下，以当前node为根的子树就是BST，所以这个子树对应的根节点就是node本身。当maxSize被更新的时候，把bestRoot同步更新为node。最后答案返回bestRoot而不是maxSize。

这个变体测试的是你能否快速把已有代码迁移到输出形态不同的题目上。注意在递归返回时，不需要返回bestRoot，只要在主方法里维护一个全局变量就行。

5.2 变体二：求最大BST子树的节点值总和

如果把题目改成“返回最大的BST子树的节点值总和”，很多人的第一反应是把size替换成sum。这个思路能走通，但有个坑：如果节点值存在负数，那么节点数最多的BST子树不一定是总和最大的。比如一棵BST子树包含了大量负值节点，节点数很多，但总和可能比一个更小的正数BST子树还低。

所以正确做法是把两个信息都维护下来：size用于合法性的状态聚合（不过目标值要用sum），同时额外维护一个sum字段。当子树合法时，sum = left.sum + right.sum + node.val。每次更新全局maxSum时，比较的是sum，但递归返回给父节点的size仍然是节点总数。这个变体很适合作为面试后的Follow Up，因为如果理解不透彻的人，往往会在这个负值问题上一脸茫然。

5.3 变体三：用迭代消灭系统递归栈

如果面试官要求不能写递归，或者想进一步考你栈模拟，可以用显式栈模拟后序遍历。核心思路是模拟“左子树入栈、右子树入栈、然后处理当前节点”的过程，在处理当前节点时，需要把左右子树的结果信息也保存在栈元素里。具体来说，可以给栈里的每个元素带上左右子树的Result结果，出栈时再合并。

不过总体而言，这道题写递归是最自然的。迭代版本的时间复杂度也是O(n)，只是空间上省去了系统递归栈，换成显式栈。面试时能主动说一句“也可以改迭代，用显式栈模拟后序”，但不要硬写，除非你提前准备过，否则现场写出冗长迭代很容易翻车。

5.4 面试加分：主动讲出复杂度分析

无论代码对不对，复杂度分析一定要主动说。每个节点在递归中只被访问一次，所以在每个节点上做的都是O(1)合并工作，总时间复杂度O(n)。空间复杂度取决于递归深度，最坏情况是链表型二叉树，递归深度O(n)；平均情况下O(h)，h为树高。如果能顺带说“这里的空间主要是调用栈，不是额外容器”，会显得你对本质很清晰。

另外可以提一句：这个解法本质上是一个树形DP，状态由子树推导，和“记忆化搜索”不是一回事，因为它没有重叠子问题，不需要缓存，纯DFS就够了。这样就把题目放到更大的算法框架里，比单纯背题要加分。

我自己的体会是，LeetCode 333最磨人的地方不是代码量，而是状态设计。Result里每一个字段都不是随便加的：isBST管合法性，size管拼接和答案，min和max管BST的全局约束。想明白这四个字段，等于把这个题做透了。如果你现在代码能背但心里发虚，建议把文章里的反例亲手推一遍递归。推完你会发现，以后再遇到类似的树形DP题，比如二叉树中的最大路径和、监控二叉树，都会顺很多。