企业官网建设流程全解析

1. 题目到底在问什么

LeetCode 333这个题号，在会员面试100题里不算冷门，但真正能一遍写对的人不多。题目描述特别简短：给定一棵二叉树，找出其中包含节点数最多的二叉搜索子树，返回这个子树的节点个数。就这么一句话，可越短越容易在理解上留坑。我见过好几个同学上来就说“这题不就是验证BST吗”，然后按照验证整棵树的思路去写，写到最后才发现子树边界、全局最大值、状态传递都要重新设计。

这个题为什么能稳坐会员面试题列表？因为它一道题同时考察了三个东西：BST性质的全局约束、递归返回值的设计能力、以及边界条件的处理。这三个点正好是树型动态规划类题目的共同难点。所以这篇我打算从题意拆解、状态设计、完整代码、边界用例、面试追问几个角度，把这道题从内到外过一遍。

1.1 “子树”不是任意连通块

“子树”这个词在二叉树里有非常严格的定义：选定某个节点作为子树的根，那么这棵子树必须包含该节点的全部后代。你只能在某个节点往下“一刀切”，不能在中间挖掉一部分节点再拼成别的形状。

这个定义会直接影响解题方向。我举个实际的例子：假设一棵树的根节点值不满足BST条件，但它左子树里有一个很大的BST，右子树里也有一个很大的BST。很多人第一反应是“我把这两个BST拼在一起，把破坏规则的根节点丢掉，节点数不是更大吗？”不行。因为丢掉根节点后，左右两部分的结构就断了，它们不再是以某个节点为根的整棵子树。这道题不允许你那样拼接。

所以做这个题时，递归函数里维护的size，一定是以某个节点为根的完整子树的节点总数。如果这棵树不是合法BST，那这个size就没有资格参与答案更新。想清楚这一点，后面写代码才不会绕晕。

1.2 BST的验证是全局约束，不是局部比较

验证BST时最容易犯的错，是只比较当前节点和左右孩子的大小。比如节点值是10，左孩子是5，右孩子是15，乍一看没问题。但BST定义要的是：左子树中的所有节点都小于根，右子树中的所有节点都大于根。也就是说，对某个节点root，它的有效取值其实是一个区间，离它越远的孩子，范围约束一点都不能放松。

举个反例：root是10，右孩子是15，右孩子的左孩子是12。只看三层的话，15大于10、12小于15都没问题。但12作为右子树的左孩子，同时也要大于根节点10。这个关系是满足的，12确实大于10。那我再换个反例：root是10，左孩子是5，左孩子的右孩子是8。8作为左子树的右孩子，必须小于根节点10，8小于10，也满足。真正的反例是这样的：root是10，左孩子是5，左孩子的右孩子是12。12在左子树里，却大于根节点10，整棵树就不是BST。但局部看5小于10、12大于5，仍然可能让人误判。

这个例子说明，判断一棵树是不是BST，不能只靠父子三层比较，必须把整个子树的最小值和最大值向上传递。自底向上方案的核心设计，就是要让每个节点向上层报告清楚子树的值域区间。

1.3 题目本质是一个“树型汇总”问题

把题目翻译成更工程化的说法：我有一棵二叉树，每个节点需要向上返回三个信息——以当前节点为根的子树是不是BST、这棵子树的最小值和最大值是什么、这棵子树有多少个节点。最终在遍历过程中，把满足BST条件的最大size记录下来。

这和LeetCode 98“验证二叉搜索树”其实是同一个递归框架，只是98只需要返回布尔值，而333还需要边界区间和size。如果你之前没有用“返回min/max”的方式写过98，建议先补一下，因为333的代码结构完全建立在那个形态上。状态设计对了，这道题的代码量其实很少；状态设计错了，代码会越写越绕。

提示：这个题收藏进“树形DP”分类里比较合适。凡是出现“子树是否满足某种性质”“子树的最大/最小值”“子树节点总数”这几个关键词，基本都可以往自底向上的状态合并方向想。

2. 解题思路的演进：从暴力到一次遍历

2.1 暴力方案为什么可行，但没必要

最简单的做法是：遍历每个节点，以它为根运行一次BST验证，记录最大值。步骤如下：

1. 前序遍历整棵树，每遇到一个节点，就把这个节点当成候选子树的根。
2. 对以该节点为根的整棵子树，做一次完整的BST验证。
3. 如果验证通过，统计节点数并更新全局答案。

这个方案思路没错，复杂度却很难看。为什么？因为每个节点都可能被祖先重复检查。假设一棵链状树深度是n，根节点验证时需要扫描几乎所有节点，根节点的左孩子验证时又要扫描它下面几乎所有节点，同一个节点被不同祖先反复遍历，最坏情况就是O(n²)。在面试现场把暴力方案说出来没问题，它至少证明你理解了题意。但说完之后一定要接一句“这里存在大量重复比较，我可以通过后序遍历把信息合并上来，把复杂度降到O(n)”，面试官会非常喜欢这个递进。

2.2 自底向上的状态合并是正解

既然祖先节点真正关心的，只是两个子树的“是否合法”“最小值”“最大值”“节点个数”，那就让每个子树在递归返回时，把这些信息全部带上来。父节点拿到左右两个孩子的信息之后，用O(1)时间就能判断自己能不能继续向上合并。

二叉树的后序遍历天然适合这个场景。后序意味着先处理完全部子节点，再处理当前节点。处理当前节点时，左右子树的所有结论已经就绪，不需要再往下钻。于是每个节点只被访问一次，总复杂度降到O(n)。

合并条件必须写完整，少一条都不行：

• 左子树是BST；
• 右子树是BST；
• 左子树的最大值小于当前节点值；
• 当前节点值小于右子树的最小值。

四条同时满足，以当前节点为根的整棵子树才是BST，才能继续向上返回信息。否则，当前节点就断掉了 BST 的链条，整棵子树不合法。但不代表左右子树内部没有合法BST，那些内部答案已经在子递归执行过程中记录到全局变量了。

这里有个关键体验：如果不设全局变量，而是在每个递归函数里都返回一个“当前子树中最大BST的size”，逻辑会很混乱。因为当当前子树不合法时，你还得把左右子树里的较大值挑出来传上去，于是返回值里又要多一个字段。我尝试过五字段版本，可以写，但读起来明显比“四字段 + 全局最大值”费劲。面试时候选代码越短越不容易出bug。

2.3 空子树的初始化是一组哨兵值

所有递归实现里，最容易翻车的点就是空节点怎么返回。我们做如下约定：

• 空节点算是一棵空的BST；
• 空子树的最小值设为正无穷；
• 空子树的最大值设为负无穷；
• 节点个数是0。

为什么要这样设？因为空节点的存在不能干扰父节点的区间判断。假设左子树为空，父节点只需要验证“当前值大于左子树最大值”。左子树最大值如果设为负无穷，那么无论当前值多大，这个比较都恒成立。同理，右子树为空时，右子树最小值设为正无穷，当前值任意小时也都满足“当前值小于右子树最小值”。这样设计之后，代码里完全不需要为“空子树”单独开分支，合并逻辑对空节点和非空节点一视同仁。

这个技巧和链表题里用哨兵节点是一个思路，都是为了省掉大量边界if判断。我记忆口诀是：空节点min给正无穷，max给负无穷，含义就是“空的不会限制你的取值区间”。

3. 完整代码实现与逐段讲解

3.1 Python版本：四字段返回值

class Solution: def largestBSTSubtree(self, root: Optional[TreeNode]) -> int: self.ans = 0 def postorder(node): if not node: # 空子树：是BST，min设为正无穷，max设为负无穷 return (True, float('inf'), float('-inf'), 0) left = postorder(node.left) right = postorder(node.right) left_is_bst, left_min, left_max, left_size = left right_is_bst, right_min, right_max, right_size = right if left_is_bst and right_is_bst and left_max < node.val < right_min: cur_min = min(left_min, node.val) cur_max = max(right_max, node.val) cur_size = left_size + right_size + 1 self.ans = max(self.ans, cur_size) return (True, cur_min, cur_max, cur_size) # 当前节点破坏了BST性质，返回False # 后面的min/max/size已经无意义，父节点的if会直接拦住 return (False, 0, 0, 0) postorder(root) return self.ans

我逐行拆一下。

主函数里定义self.ans作为全局最大值，方便后序函数直接更新。如果不用成员变量，也可以返回一个长度为4的数组，把最优值塞在数组最后一个位置，但那种写法可读性差，我还见过有人因此把索引写错，不建议。

postorder这个匿名函数，返回一个固定格式的四元组。空节点返回(True, float('inf'), float('-inf'), 0)，前面解释过，只为了让左最大和右最小比较恒成立。

递归处理左右孩子之后，把四元组解包成六个变量。真正做判断的只有一行：三个条件同时成立。left_max < node.val 保证了左子树所有节点都严格小于当前节点；node.val < right_min 保证了当前节点严格小于右子树所有节点。这里必须用严格小于，不能用小于等于，因为LeetCode默认BST不允许相等值破坏规则。

条件成立时，以当前节点为根的子树是合法BST。那么新子树的最小值，应该是左子树最小值和当前值中较小的那一个；新子树的最大值，应该是右子树最大值和当前值中较大的那一个。这个看上去很简单，却是很多人会写错的地方。有人容易写cur_min = min(node.left.val, node.val)，这样在左子树为空时没问题，一旦左子树有三层，最小节点可能藏在更深的地方，就出错了。

条件不成立时，直接返回(False, 0, 0, 0)。有人会问，这里要不要把左右子树中已知的最大BST size传上去？不用，因为那个值已经更新到self.ans里了。这个返回值唯一的作用是告诉父节点“以我为根的子树已经不合法”，至于min/max填什么，父节点检查到False后不会使用。所以这里填0是完全安全的。

还有一点要注意：self.ans的更新时机必须放在条件成立的分支里。因为只有被验证为合法BST的子树的size才计入答案；如果放在函数开头或者条件外的位置，会把不合法子树的size也算进去，结果必然错误。

3.2 Java版本：用Info类代替Tuple

Java里没有Python这么方便的元组，常见的写法是自己定义一个小类。我很推荐在面试里定义Info类，因为它字段命名清晰，读代码的人一眼能看懂每个字段的含义。不推荐用int[4]数组一次性返回，因为下标0/1/2/3分别对应什么，过三天自己都容易忘。

public class Solution { private class Info { boolean isBST; int min; int max; int size; Info(boolean isBST, int min, int max, int size) { this.isBST = isBST; this.min = min; this.max = max; this.size = size; } } private int ans = 0; public int largestBSTSubtree(TreeNode root) { dfs(root); return ans; } 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); if (left.isBST && right.isBST && left.max < node.val && node.val < right.min) { int size = left.size + right.size + 1; ans = Math.max(ans, size); return new Info(true, Math.min(left.min, node.val), Math.max(right.max, node.val), size); } return new Info(false, 0, 0, 0); } }

Java版本里有一个小细节：空节点返回Integer.MAX_VALUE和Integer.MIN_VALUE作为哨兵值。只要题目里的节点值限制在int范围内，这套就成立。如果面试官出题时故意说节点的val可以覆盖到long，那就要把int换成long，或者改用Python的float('inf')，否则会溢出。

3.3 如果题目改成“输出最大BST的根节点”

这个变体很常见。基本思路不变，只是多维护两个变量：一个是最大size，另一个是对应子树的根节点。

class Solution: def largestBSTSubtreeRoot(self, root: Optional[TreeNode]) -> Optional[TreeNode]: self.best_size = 0 self.best_root = None def postorder(node): if not node: return (True, float('inf'), float('-inf'), 0) left = postorder(node.left) right = postorder(node.right) if left[0] and right[0] and left[2] < node.val < right[1]: cur_size = left[3] + right[3] + 1 if cur_size > self.best_size: self.best_size = cur_size self.best_root = node return (True, min(left[1], node.val), max(right[2], node.val), cur_size) return (False, 0, 0, 0) postorder(root) return self.best_root

更新根节点的条件要看清楚：cur_size > self.best_size。如果改成不小于，当出现多个同样大小的BST时，根节点会被后出现的覆盖掉。该选哪一个，取决于题目要求。通常面试官不会把这个约束说死，你可以按“保留先遇到的”或“保留后遇到的”处理，只要讲清楚你的规则即可。

4. 边界用例与实测细节

4.1 空树和单节点

测试空树时，递归不会进入任何节点，自始至终没有更新ans，函数返回0，正确。单节点树只需要注意一点：空左子树返回值里的min是正无穷，空右子树返回值里的max是负无穷，所以判断条件变成left_max(负无穷) < node.val < right_min(正无穷)，必然成立，于是ans被更新成1。这里如果哨兵值设反了，比如空节点min设成负无穷，那么对单节点树，node.val < right.min会变成node.val < 负无穷，直接判错，ans永远为0。所以初始化方向要认真记牢。

4.2 链状树其实也是BST

再强调一次，BST不要求平衡。一棵树如果形态是一条向右的链，比如1 -> 2 -> 3 -> 4 -> 5，那么它的中序遍历是1、2、3、4、5，严格递增，整棵树都合法，答案应该是5。同理，递减链5 -> 4 -> 3 -> 2 -> 1的中序遍历是5、4、3、2、1，严格递减，它也是BST吗？是的，BST只要求中序遍历有序，升序降序按无妨？这里要小心：BST的标准定义是左子树所有节点值小于根，右子树所有节点值大于根。如果整棵树是向右延伸的递减链，根节点5的右孩子是4，要求5 < 4，满足吗？不满足。所以递减链不是BST。

我举个例子来说明：如果一棵树是root=5，right=4，right.right=3，那它不满足“右子树所有节点大于根节点”，因为右子树里出现了小于5的4。整棵树不是BST。但局部看，4的右孩子是3，仍然不满足4 < 3，所以节点4往下的子树也不是BST。最终答案就是单节点size 1。这个用例可以很快测出你对BST区间约束是否理解到位。

在实际测试时我会准备这样一张用例表：

4.3 全等值节点的陷阱

考虑四个节点值全是2的情况。假设结构是root=2，root.left=2，root.right=2。按照LeetCode默认的严格BST定义，左边出现的2必须严格小于根节点2，但2小于2是假的，所以左子树与根合并失败。同理右边也失败。只有单个节点本身算BST，所以答案应该是1。

如果面试官追问“BST是否允许相等值”，你可以说：标准LeetCode定义不允许，但如果限定改成左子树所有节点小于等于根，右子树所有节点大于根，那答案是3。修改起来也很简单，把合并条件里的left_max < node.val改成left_max <= node.val，把node.val < right_min改成node.val <= right_min。这种可配置的定义方式，说明你真正理解了题目的可变部分。

4.4 左右子树都合法，根节点破坏条件

这是最常见的埋雷场景。构造这样一棵树：root是10，左子树是以5为根的大小为3的BST，最小值1，最大值8；右子树是以15为根的大小为2的BST，最小值7，最大值15。注意右子树里的最小节点7小于10。

在合并时，left.max是8，小于10，条件成立；但right.min是7，那么10 < 7为假，于是根节点这层合并失败，答案不能是3+2+1=6。正确的答案是max(左子树中的3，右子树中的2)，也就是3，这个结果已经在递归到左右孩子时就记录到ans里了。

这类用例对我来说是必测项。它考察的就是“当前节点不合法时，答案是否已经被子递归提前保存”这一关键逻辑。如果ans更新时机写错，这种用例立刻暴露问题。

5. 面试追问与场景扩展

5.1 为什么必须后序遍历

面试官经常会问：你用的是什么遍历方式？答案是后序遍历。原因在于，父节点判断自己能否构成BST时，需要依赖子树的min/max以及isBST标记，而这些信息只有在子树处理完之后才存在。如果改成前序，你会在还没拿到子树信息时就去判断，思路就不成立。中序在这个特定问题上也不是最优，因为BST的中序遍历应该有序，但你依然无法在O(1)时间内知道子树节点数变化后的min/max边界。后序是结构上最自然的。

5.2 如果树特别深，递归栈爆了怎么办

这个问题在真实面试里是一个加分追问点。递归方案的空间复杂度是O(H)，H是树高。最坏情况下，树退化成一长链，H=n，递归深度可能达到n，这在一万级节点上没问题，但在上百万节点时可能爆栈。

解决思路是用显式栈模拟后序遍历。需要自己维护一个类型为Info的映射表，在遍历过程中记录每个节点左右子树的计算结果。还有一个常用技巧是“两次遍历法”：第一次用一个栈把节点按后序顺序输出，第二次再逆序处理结果。因为核心的合并逻辑没变，所以只要理解递归版本，改成显式栈只是把系统栈换成自己的栈。

5.3 如果还要求最大子树的节点值总和

这是同一个模板的简单扩展。Info结构体里再加一个sum字段。合并成功时，新sum等于左子树的sum加右子树的sum加当前节点值。答案的更新条件可以按照题目要求改成“sum最大”，而不是“size最大”。这个扩展能考查你是否真的理解了自底向上状态设计，而不是只会背代码。

5.4 如果存在多个大小相同的最大BST

按严格“最大size”的语义，输出大小即可，不需要输具体路径，那就无所谓。但如果扩展成找根节点，就要明确使用大于还是大于等于。我一般写成大于，这样在遇到多个一样大的候选时，保留第一次遇到的根节点。面试时只要把规则说清楚，面试官不会在这个细节上难为你。

5.5 能不能用记忆化搜索解决

这个问题值得想清楚。有些人会尝试对每个节点做“以该节点为根的子树的验证结果”做记忆化，再遍历所有节点取最大。看起来像是优化了暴力方案，但仔细一想，验证BST需要知道整棵子树的min/max，这个记忆化本身还是得靠后序状态传递。既然后序已经把结果算出来了，再多加一层记忆化就是重复工作，纯属画蛇添足。能自动想到这一点的同学，说明对递归状态有感觉，但最好在表达时说明：记忆化在这里没有必要性，因为它已经被后序的一次遍历天然覆盖了。

6. 复盘：这道题要记住的核心收益

最后分享一点我自己的复习经验。

第一次做这个题，我写的是暴力方案：每个节点单独验证，然后取最大值。在本地小规模测试上能过，但提交后性能告警很大。那时候我没意识到真正的问题出在重复遍历，而不是代码逻辑。后来在一次模拟面试里被面试官追问“能不能优化到一次遍历”，我才认真把状态合并思路顺清楚，发现自己之前对递归返回值的理解太弱。

第二次重做，我用了四字段后序方案，代码20行左右。之后我又把98题、333题以及一个变体“最大BST和”放在一起复盘，才发现这三题的骨架一模一样：子树是否合法、子树边界、子树统计量，三个信息打包上传，父节点落地判断。这个认知比会写333本身值钱得多，因为后面刷树形DP类题目，十道里有七八道都是这个套路。

如果你想检验自己是不是真的会了，我建议不看代码，把下面三个问题都答一遍：

1. 空节点返回的min和max为什么一个是正无穷一个是负无穷。
2. 当前节点不合法时，为什么可以直接返回空值，而不会丢答案。
3. 如果要求输出最大BST根节点，你会在哪里更新记录、用大于还是大于等于。

这三个问题答顺了，这个题才算真正过关。面试过得稳不稳，往往就差在这些容易忽略的细节上。