企业官网建设流程全解析

刷 LeetCode Hot 100 刷到第 41～50 题，我的第一反应是：这批题目像是一道分水岭。前面 40 题里字符串、数组、链表轮番上阵，到了这个区间，二叉树突然成了绝对主角——十道题里有七道是树，剩下两道分别是贪心和动态规划。很多人在这个位置会明显感觉到刷题速度变慢，倒不是题目突然变难了，而是递归思维第一次被系统化地、反复地考察，同样一个"把问题交给子树"的思路，在不同题目里居然有完全不一样的写法。

不过先别被"树题"劝退。这十道题里没有哪一道是真正的压轴难题，它们更像是把二叉树最核心的几块基础能力——遍历、递归、BFS——做成了一组标准动作，让你一遍一遍练到肌肉记忆。如果你正在准备面试，或者刚开始做 Hot 100 的"hot100题"清单，41～50 绝对值得单独慢下来刷；尤其是第 42 题"不同的二叉搜索树"，它就是热词里那个"hot100动态规划"的代表题目，一个状态定义学明白，后面好几道 DP 都能跟着受益。

这篇文章我不打算从头到尾念题解，而是按我当时刷题的顺序和心态，把这十道题拆成三块：两块非树题单独处理，八道树题分成"模板型"和"递归进阶型"两组。每道题给可以直接用的代码和复杂度，重点讲讲哪些坑是提交之后才发现的、哪些判断是网上题解里没写透的。

1. 先看整体布局：为什么 41-50 被称为树题练功房

1.1 十道题的分布与考点一览

不同版本的 Hot 100 顺序会有微调，我这里按 LeetCode 中文站长期使用的一个经典排序来聊。这个区间覆盖的恰好是"字符串 + DP + 二叉树"的过渡段，整体分布如下：

可以看到，链表的题在 41 之前基本结束，树的题从这里开始成建制出现。我认为这个顺序不是随机的：前面的数组、字符串、链表题目单点考察某个数据结构；而树题天然要求你同时掌握"遍历框架"和"递归返回值设计"两件事，这是从"会写代码"到"会设计递归"之间的一个台阶。

1.2 这个批次真正想考察的能力

如果只盯着题目本身，容易陷入"每道题背一个解法"的误区。刷完这一组后我的体会是，41-50 真正训练的是三个能力：

• 分类能力：看到题目先判断它属于树的哪种操作——是遍历、搜索、修改结构，还是统计信息。
• 递归语义设计能力：写递归函数之前，先想清楚"这个函数返回什么"。第 49 题返回高度、第 50 题返回节点，两者返回值含义不同，代码形态就完全不同。
• 模板记忆能力：层序遍历的 BFS 模板、中序遍历的迭代模板，几乎原封不动会出现在后续很多难题里。

带着这个框架去刷，而不是机械地"看题-看题解-抄代码"，这批题的价值会大很多。

2. 非树题先拆掉：贪心和动态规划各来一道

2.1 划分字母区间：看起来像滑动窗口，其实是贪心

第 41 题"划分字母区间"（Partition Labels）给一个字符串，要求把它切成尽可能多的片段，使得每个字母在同一个片段中只出现一次。题目给的例子是"ababcbacadefegdehijhklij"，输出[9, 7, 8]。

我第一次做这题时想当然地用了滑动窗口，维护一个窗口、判断窗口里的字符在窗口外有没有重复，结果写出来又慢又容易错。后来意识到，正确思路是贪心，而且步骤非常简单：

1. 先遍历一遍字符串，记录每个字符最后一次出现的下标last[ch]。
2. 再从前往后遍历，维护当前片段的右边界end，不断用max(end, last[ch])更新它。
3. 当i == end时，说明当前片段里所有字符都不会在后面出现了，就在这里切一刀。

核心代码（Python）：

def partition_labels(s: str) -> list[int]: last = {} for i, ch in enumerate(s): last[ch] = i ans = [] start, end = 0, 0 for i, ch in enumerate(s): end = max(end, last[ch]) if i == end: ans.append(end - start + 1) start = end + 1 return ans

为什么这是贪心而不是双指针？因为这里有一个可证明的贪心选择性质：当扫描到i == end时，当前片段已经满足"所有字符都不在后面出现"，此时切片是最优的。如果你不切，继续往后扩展，就会把本来可以独立成段的字符吞进来，片段数只会更少。由于题目要求"尽可能多的片段"，所以能切就切，绝不会错。

复杂度是 O(n) 时间和 O(1) 空间（因为字符集是固定的 26 个字母，last字典大小有上限）。这题在面试里属于"讲清楚为什么"比"写出代码"更重要的题目，建议把贪心正确性用一句话说给面试官听："每个片段闭合点就是当前最大 last 下标，扫描到这个点时所有字符都已最后出现。"

2.2 不同的二叉搜索树：hot100 动态规划的"状态定义"教科书

第 42 题"不同的二叉搜索树"是热词里 "hot100动态规划" 最常被点名的题目之一。题目问：给定整数 n，求由 1 到 n 为节点值组成的不同二叉搜索树有多少种。

这题我第一次看的时候完全没头绪，因为"数数量"和"建树"不一样，不需要把每棵树列出来。事实上它是个非常经典的计数 DP：

• 设dp[n]表示 n 个连续整数能组成的 BST 数量。
• 任选一个整数 i 作为根，左子树由i-1个数组成，右子树由n-i个数组成。
• 左右子树的数量相互独立，所以组合数为dp[i-1] * dp[n-i]。
• 对所有的 i 求和，就是dp[n]。

边界条件是dp[0] = 1，因为空树算一种。代码如下：

def num_trees(n: int) -> int: dp = [0] * (n + 1) dp[0] = 1 for i in range(1, n + 1): for j in range(1, i + 1): dp[i] += dp[j - 1] * dp[i - j] return dp[n]

这个递推式的组合意义要反复体会：dp[j-1]是左子树的数量，dp[i-j]是右子树的数量，两者相乘是因为左右子树的结构互不影响。这是典型的"乘法原理 + 枚举根节点"的 DP 设计模式，后面很多树形 DP 都是从它衍生出来的。

另外，这个数列其实就是卡特兰数（Catalan Number），通项是 C_n = (2n)! / ((n+1)! n!)。如果你在面试中被追问，提一句"这组数对应卡特兰数"会加分，但没必要真去算阶乘——O(n²) 的 DP 已经是最稳妥的写法。

2.3 这两道题放在一起给我的启发

把 41 和 42 放在一批刷，我最大的感受是：贪心和 DP 的边界其实很清晰。贪心是在每一步做局部最优选择并且这个选择能保证全局最优；DP 则是枚举所有可能的结构（比如枚举根节点），用状态递推累加。第 41 题你没法用 DP 枚举"切了几段"，因为段与段之间是顺序相连的，状态定义会很别扭；第 42 题你也很难用贪心选一个"最优根"，因为所有根都要统计。

所以遇到这类题目，先问自己一个问题：这是个"选一个方案"（贪心）还是"数所有方案"（DP）？这个问题一问对，方向就错不了。

3. 二叉树模板组：验证、层序、中序、最大深度

3.1 验证二叉搜索树：只比较父子节点是必错的

第 43 题"验证二叉搜索树"是个经典的陷阱题。很多新手会写这样的逻辑：

if root.left and root.left.val >= root.val: return False if root.right and root.right.val <= root.val: return False

这个写法只看父子两点，遇到下面这种树就会错：根节点 5，左子树里有个节点值是 6，右子树里有个节点值是 3。每个父子关系都满足，但整棵树不是 BST，因为左子树里出现了比 5 大的节点。

正确的做法是给每个节点传一个允许的取值范围(low, high)，递归时收紧范围：左孩子继承(low, root.val)，右孩子继承(root.val, high)。代码：

def is_valid_bst(root) -> bool: def dfs(node, low, high): if not node: return True if node.val <= low or node.val >= high: return False return dfs(node.left, low, node.val) and dfs(node.right, node.val, high) return dfs(root, float('-inf'), float('inf'))

另一个更隐蔽的坑是：题目默认 BST 中节点值互不相同，所以判断条件用<=/>=；如果允许重复值（虽然 Hot 100 原题不涉及），边界条件要根据题目要求改成</>。被测试用例教做人的时候，多半就是这里。

迭代版的思路等价于中序遍历。BST 的中序遍历结果必须是严格递增的，所以你也可以用栈做中序遍历，同时记录前一个节点的值，一旦发现当前值不大于前值就返回 False。这个写法在"恢复二叉搜索树"这类进阶题里很常用，建议两个版本都掌握。

3.2 层序遍历：BFS 模板的"快照"细节

第 44 题"二叉树的层序遍历"要求按层输出，这是 BFS 最标准的应用场景。模板如下：

from collections import deque def level_order(root): if not root: return [] q = deque([root]) res = [] while q: level = [] for _ in range(len(q)): # 关键：先快照当前层的长度 node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res

这个模板最核心的细节是那句for _ in range(len(q))。len(q)在进入 for 循环那一刻求值，它代表的是当前层的节点数。如果你写成while q:然后直接 popleft，队列里会混入下一层的节点，两层数据就糊在一起了。这个"快照长度"的技巧，在树的锯齿形遍历、右视图、填充 next 指针等一系列题里都会反复用到，属于必须形成肌肉记忆的点。

复杂度方面，每个节点入队出队一次，时间 O(n)，最坏情况下空间 O(n)。

3.3 中序遍历：递归、迭代、Morris 怎么选

第 45 题"二叉树的中序遍历"看似简单，但它考察的是你对栈的运用。递归版人人都能写，但面试里往往要求你写迭代版，因为递归体现不了空间控制能力。

迭代版的核心是模拟递归栈的行为：一路向左压栈，弹出来访问，然后转向右孩子。

def inorder_traversal(root): res = [] stack = [] cur = root while stack or cur: while cur: stack.append(cur) cur = cur.left cur = stack.pop() res.append(cur.val) cur = cur.right return res

这个写法我最初容易错在没有cur = cur.right这行，导致弹出节点后流程原地打转。记住：cur永远指向"下一个要处理的节点"，而不是"刚访问完的节点"。

至于 Morris 遍历，利用线索二叉树做到 O(1) 空间，实际面试极少要求，但如果你能在聊天里说出它的思路——"把右子树的最左节点的后继指回当前节点，遍历完再还原"——会显得你理解很深。

3.4 最大深度：base case 是 0 不是 1

第 46 题"二叉树的最大深度"就是一行递归：

def max_depth(root): if not root: return 0 return max(max_depth(root.left), max_depth(root.right)) + 1

深度定义为从根到最远叶子节点的节点数，所以空节点返回 0，叶子节点在递归结束后自然得到 1。这个 base case 很多人会手滑写成if not root: return 1，结果整棵树的深度全部偏大。记住：空树深度是 0，不是 1，因为节点数统计里没有节点。

这题也可以用层序遍历数层数，但递归解法更简洁，而且它是理解第 49 题"直径"的地基。

4. 二叉树进阶组：翻转、对称、直径、最近公共祖先

4.1 翻转二叉树：最像"照抄模板"的一题

第 47 题"翻转二叉树"给每棵子树交换左右孩子即可。递归写法：

def invert_tree(root): if not root: return None root.left, root.right = root.right, root.left invert_tree(root.left) invert_tree(root.right) return root

这题在 Hot 100 里是"简单"评级，但它最值得练的是递归出口和返回值的配合：先交换当前节点的左右孩子，再递归处理子树，最后返回当前节点作为新根。你不返回root而返回root.left或者不返回，都会导致上层拿到的子树是错的。

它之所以出名，是因为 Homebrew 作者当年在面试时被这题刷掉，后来引发了一场关于"面试造火箭、工作拧螺丝"的大讨论。但从刷题角度讲，这题就是用来练手感的，别想太多。

4.2 对称二叉树：不是比较一次就完事

第 48 题"对称二叉树"问的是一棵树是否以根节点为轴镜像对称。很多人上来就对比root.left和root.right完事，但那只检查了第一层。正确做法是递归比较两棵子树：左子树的左孩子 对 右子树的右孩子，左子树的右孩子 对 右子树的左孩子。

def is_symmetric(root): def check(p, q): if not p and not q: return True if not p or not q: return False return p.val == q.val and check(p.left, q.right) and check(p.right, q.left) return check(root, root)

这里的"镜像对"映射关系是最容易记混的地方。我的记忆方法：两个人面对面站，你的左手对着对方的右手，所以对称比较是左对右、右对左。这个类比一出，代码基本不会写错。

迭代版可以把它改造成队列 BFS，每次成对地弹出两个节点比较，本质是同一个递归逻辑的循环化。

4.3 二叉树的直径：递归返回的是高度，答案藏在全局变量里

第 49 题"二叉树的直径"是这批题里我收获最大的一题。它求的是任意两个节点之间边的数量的最大值。注意是边数不是节点数，所以两个节点本身不把起点算进去。

核心思路是：对于任意一个节点，经过它的最长路径长度 = 左子树最大深度 + 右子树最大深度（这里的最大深度用边的数量衡量）。所以我们在递归计算每个节点深度的过程中，顺手用全局变量记录这个和的最大值。

def diameter_of_binary_tree(root): res = 0 def depth(node): nonlocal res if not node: return 0 left = depth(node.left) right = depth(node.right) res = max(res, left + right) return max(left, right) + 1 depth(root) return res

这题的坑在于：递归函数返回值是子树的高度，而答案并不直接从这个返回值里取，它藏在一个每次递归都更新的全局变量里。第一次写的时候我很自然地想return max(left, right) + 1就是答案，结果连题目示例都对不上。后来才明白，直径不一定经过根节点，它可能完全落在某棵子树里，所以必须全局比较。

在 C++ / Java 里，你需要用成员变量或者传一个 int 数组来模拟这个全局变量；Python 的nonlocal是最舒服的写法。另外注意这是"边数"，所以left + right没有额外加 1；如果题目改成问节点数，就要在left + right + 1处处理。这种"题目定义差一个字，答案差一个 1"的情况，是面试官最爱埋的雷。

4.4 最近公共祖先：让递归帮你"往上带话"

第 50 题"二叉树的最近公共祖先"是整个 41-50 里最能体现递归返回值设计功力的一题。题目给定一棵普通二叉树和两个节点 p、q，要找它们的最近公共祖先。

递归函数的设计思路非常巧妙：函数返回的语义不是"子树里有什么值"，而是"这棵子树里是否找到了 p 或 q，以及找到了哪个"。具体规则：

• 如果当前节点是空，返回空。
• 如果当前节点等于 p 或 q，就返回当前节点，表示"找到了目标"。
• 递归左右子树，结果分别是 left 和 right。
• 如果 left 和 right 都不为空，说明 p 和 q 分别位于左右子树，当前节点就是 LCA，返回当前节点。
• 如果只有一个非空，就把这个非空结果向上返回，表示"这棵子树里只找到一个目标，继续往上带话"。

def lowest_common_ancestor(root, p, q): if not root or root == p or root == q: return root left = lowest_common_ancestor(root.left, p, q) right = lowest_common_ancestor(root.right, p, q) if left and right: return root return left or right

"带话"这个类比是我后来重构思路时找到的：每个递归调用就像一个小信使，它只向父节点报告"我这边有没有找到目标"。如果两边都报告找到了，父节点就知道自己是汇聚点；如果只有一边报告，就把这个报告继续往上传。理解到这个层面，你不仅会写这道题，而且能迁移到"树里找某个路径""判断子树包含关系"等一系列问题。

注意这题的前提是 p、q 一定在树里，所以函数不需要处理"找不到"的情况。如果题目额外要求"不存在时返回空"，逻辑就要加哨兵判断，别搞混。

5. 提交时最容易踩的坑与排查思路

5.1 树题的高频 bug：空指针、忘记递归出口、死循环

刷完这十道题，我把树题常见的错误整理成了一张自查表：

树题 debug 时最有效的工具是：在递归函数里加打印参数——打印当前节点的值和当前深度，然后逐步缩小范围。不要靠肉眼瞪代码，递归走得越深越容易眼花。

5.2 DP 下标的边界自查方法

第 42 题的动态规划虽然代码短，但边界错了会很难发现。我总结了一个通用自查法：

• 先问自己dp[0]应不应该有定义。这道题里空树算一种，所以dp[0] = 1。
• 再问枚举范围：内层j从 1 到i，能不能取到i？可以，因为取i意味着根是最右节点，左子树有i-1个节点，右子树为空。
• 最后验证小样本：手算dp[1] = 1，dp[2] = 2，dp[3] = 5，和已知卡特兰数的前几项对照。

DP 题最怕"样例过了但是大数据挂了"，一般就是整型溢出或者数组越界。第 42 题如果 n 较大，dp的值会迅速膨胀，C++ 里要用long long，Python 则无所谓（自动大整数）。面试时多嘴问一句 n 的范围，能帮你提前规避这个坑。

5.3 一套我自己常用的手动验证方法

面对树题，我有一个坚持的习惯：每次写递归之前，先在草稿纸上画一棵深度为 3 的小树，把递归函数的输入、输出标注在节点旁边。比如写第 50 题时，我会在根节点旁边写"左右都非空，返回根"，在叶子节点旁边写"等于 p，返回自身"。这个动作看起来很笨，但它能逼你把递归语义想清楚，比直接写代码快得多。

另一个方法是用"极小用例驱动"：先把root = None的情况跑通，再跑单节点树、两节点链式树、三节点完全树。这几个极端 case 全部通过后，才有把握去提交。

6. 刷完 41-50 之后的复盘方式与节奏建议

6.1 七天消化方案参考

如果是从零开始刷这批题，我建议不要一天十道。我的实际安排是：

• 第 1 天：只刷 41、42，重点吃透贪心和 DP 的原理，每道题自己对着空编辑器重写一遍。
• 第 2 天：刷 43、44、45，这三道是树的遍历基础，必须能把模板默写出来。
• 第 3 天：刷 46、47、48，把递归的手感练熟，三题可以一口气完成。
• 第 4 天：刷 49、50，这两道是递归设计题，值得各花一整块时间琢磨。
• 第 5 天：不看答案，把十道题全部重写一遍，记录卡壳的题。
• 第 6 天：只看卡壳题的题解，画出递归树，重新实现。
• 第 7 天：做一轮"快速过题"，每道题只看题目描述，在纸上写出核心思路，不敲代码。

这个节奏的核心理念是：新手最忌讳"连续刷题不复习"，第一天刷的题第七天早就忘了。间隔重复才能把递归模板沉淀成肌肉记忆。

6.2 收藏夹里的"错题集"怎么建

我在刷 Hot 100 时维护了一个本地文档，按"题目 + 我的错误 + 正确思路的一句话总结"记。比如这十道题我记下来的内容是：

• 41 划分字母区间：先记录 last 下标，再扫一遍贪心切分。
• 42 不同的二叉搜索树：枚举根节点，左右子问题的数量相乘再累加。
• 43 验证 BST：范围限制法，不是只看父子。
• 44 层序遍历：BFS 模板先快照 len(q)。
• 45 中序遍历：while stack or cur，cur 指向下一个该处理的节点。
• 46 最大深度：空节点返回 0。
• 47 翻转二叉树：交换左右孩子，返回 root。
• 48 对称二叉树：左对右、右对左。
• 49 直径：递归返回高度，全局变量记录路径最大边长。
• 50 最近公共祖先：返回值语义是"是否找到目标，找到了哪一个"。

这些一句话总结，比摘抄整段官方题解有用得多，因为它是从你自己的错误里长出来的。

最后再分享一个经验：树题的代码量普遍很小，难度全在"想清楚再写"这个过程里。刷这批题时不要急着追求一次性 AC，多花三分钟把递归函数返回什么、什么时候 return、什么时候更新全局变量想明白，远比节约这两三分钟更划算。41-50 是 Hot 100 里树主题的集中预热，把这些递归思路练扎实，后面遇到二叉树展开为链表、路径总和、二叉树的序列化等难题时，你会发现自己已经储备了足够多的"思维武器"。