企业官网建设流程全解析

LeetCode Hot100刷到第28题了，题目是104. 二叉树的最大深度。说实话，这道题在Hot100里面属于“送分题”级别的难度，但它背后牵扯出来的东西一点都不简单：二叉树的遍历、递归分治、迭代模拟、层序扩展，几乎每个核心考点都能从这题顺藤摸瓜摸出来。我刷题这几年，遇到很多人在二叉树题目上反复栽跟头，其实根子就是在这类最基础的题目上没吃透。

这道题要做什么，一句话就能说清楚：给一棵二叉树的根节点root，返回这棵树的最大深度，也就是从根节点到最远叶子节点路径上的节点总数。空树深度为0，只有根节点深度为1。看起来人畜无害，但它是后面一连串二叉树题目的地基，比如判断平衡二叉树、求二叉树直径、N叉树最大深度，全都是从这一个模板上长出来的。

这篇内容适合三类人看：刚开始刷LeetCode、二叉树遍历还没完全捋清楚的初学者；想面试前快速把树的深度、高度、直径、平衡判断这些相关题串起来的人；以及写二叉树程序经常报运行时错误、想搞清楚排查思路的人。我会把四种常见解法全部拆开来讲，连同递归边界、栈溢出的坑、BFS的层数边界、本地调试技巧一起聊清楚。

1. 题目解读与核心思路盘点

1.1 题面中容易忽略的两个定义

先看题面和关键定义。LeetCode官方对这题的描述是：给定一个二叉树root，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

这里有两个地方值得抠字眼。第一个是“叶子节点”的定义：叶子节点是没有子节点的节点，所以如果一棵树只有一个根节点，那么根节点本身就是叶子，深度是1。第二个是“节点数”而不是“边数”，从根到一个深3的叶子经过3个节点，中间隔着2条边，如果面试官问的是“高度”或者“路径长度”，有可能用的是边的数量，一定要先跟对方确认口径。

还有一个新手特别容易绕进去的误区，就是把左右子树深度相加再+1，求出来的是经过根节点的“总节点路径”而不是最大深度。正确答案是取左右子树深度的最大值再+1。我见过不少人在这上面翻车，本质上是没有想清楚“深度是单条路径的长度”这件事。

1.2 三条主线思路：分治、模拟递归、逐层计数

最大深度的求解思路可以归成三大类，每一类对应一个不同的思维方式。

第一类是递归后序遍历，也叫自底向上的分治。子树深度先算出来，当前节点再取最大值+1。这最贴合问题本身的递归结构，代码极简，是大多数人第一反应就能写出来的方案。

第二类是迭代DFS，用栈手动模拟递归过程。递归的本质是系统栈帮我们保存了“当前节点走到哪一层”的状态，迭代就是把这份状态显式地存下来。常见的做法是节点和深度一起入栈，边遍历边更新最大深度。

第三类是BFS层序遍历，用队列逐层扫描。森林里数一棵树有几层，本质上就是在求这棵树的最大深度。队列每处理完一层计数器加1，最终计数器的值就是答案。

这三类思路的时间复杂度都是O(n)，因为无论怎么遍历，每个节点至少访问一次。差别主要体现在空间复杂度上：递归和迭代DFS的额外空间取决于树的高度，BFS的额外空间取决于树的宽度。后面我会逐个展开。

2. 递归解法：用分治思想写最简洁的代码

2.1 后序遍历的三步写法与执行过程

递归解法是这道题最主流的写法。以Java为例，最清晰的是拆开写的版本：

class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); return Math.max(leftDepth, rightDepth) + 1; } }

递归写法的核心就三步。第一步确定入参和返回值：入参是当前节点，返回值是当前子树的最大深度。第二步确定终止条件：节点为null时返回0，这既是空树的答案，也是递归触底反弹的出口。第三步确定单层逻辑：先拿左子树深度，再拿右子树深度，取较大值加1作为当前节点深度。

用一棵具体的小树走一遍过程就清楚了，假设树的结构是节点1的左孩子是2，右孩子是3，节点2没有子节点，节点3的左右孩子分别是4和5。执行maxDepth(1)，会先递归到节点2，节点2的左右递归都返回0，所以节点2返回1。接着递归到节点3，节点3的左子树返回1，右子树返回1，节点3返回2。回到根节点，取Math.max(1, 2) + 1得到3，整棵树的最大深度就是3。

这就是典型的后序遍历顺序：左子树处理完，右子树处理完，最后才轮到当前节点“汇总”。如果你画一下调用栈的进出顺序，会发现它和标准的left-root-right后序遍历完全一致。

2.2 复杂度分析和递归栈的边界

复杂度方面，时间上每个节点访问且仅访问一次，所以是O(n)。空间上递归的消耗主要是系统调用栈，栈的深度等于树的高度而不是节点数。平衡二叉树高度是O(log n)，如果二叉树退化成一条单链，高度就是O(n)，递归深度也跟着变成O(n)。

这里的O(n)空间是递归解法最容易被追问的点。面试官经常会问：如果这棵树有10万个节点，并且退化成单链，递归会怎样？答案是可能栈溢出，因为系统栈的容量有限。虽然LeetCode绝大多数用例不会把树构造成会爆栈的深度，但你要在面试现场主动说出来，这能体现你对递归本质的理解。

还有个小细节，这道题返回值是int，就算树高10万，int也完全放得下，不需要担心数据范围。真正需要警惕的是双向递归时可能重复计算，但这题没有重叠子问题，每个节点只算一次，不需要记忆化搜索。

2.3 递归最容易踩的三个坑

第一个坑是终止条件没写好。有人上来就写if (root == null) return 1，整个答案直接翻倍飘了。还有人漏掉null判断，一进函数就访问root.left，运行起来必报NullPointerException。

第二个坑是忘记加1。Math.max(leftDepth, rightDepth)算完直接return，结果永远停在0，因为底层的null子节点返回0后，上面每一层都没能把这一层的存在计入答案。

第三个坑是把返回值和“当前遍历深度”混在一起。这两种不是一个东西：递归返回值表达的是子树高度，是一层一层“归”出来的；而当前深度是往下“递”的时候带进去的参数。这道题要的是前者。调试的时候可以在递归入口临时加打印语句，每进入一个节点打印节点值和当前参数，看一遍调用顺序，比自己盯着代码猜要快得多。

3. 迭代解法：不靠系统栈，手动模拟DFS与BFS

3.1 栈模拟DFS：节点和深度一起入栈

递归有栈溢出的风险，那就用迭代来绕开。DFS迭代的一种优雅做法是拿两个栈，一个存节点，一个存这个节点对应的深度。

class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } Deque<TreeNode> nodeStack = new ArrayDeque<>(); Deque<Integer> depthStack = new ArrayDeque<>(); nodeStack.push(root); depthStack.push(1); int maxDepth = 0; while (!nodeStack.isEmpty()) { TreeNode node = nodeStack.pop(); int depth = depthStack.pop(); maxDepth = Math.max(maxDepth, depth); if (node.left != null) { nodeStack.push(node.left); depthStack.push(depth + 1); } if (node.right != null) { nodeStack.push(node.right); depthStack.push(depth + 1); } } return maxDepth; } }

为什么要把深度一起入栈？因为栈只能帮我们记住“下一步该处理谁”，但记不住“这个节点在第几层”。递归时系统栈默认保存了调用现场，我们把它搬到显式栈里就得把深度这个附加信息也存下来。如果你不想用双栈，可以用一个Deque存int[]数组，数组第一个位置是节点编号，第二个是深度，效果一样。

这段代码里先压左还是先压右其实无所谓，因为深度的计算是跟着节点走的，不是跟着“遍历到哪一步”走的。我习惯先压右再压左，这样出栈顺序是根->左->右，更像前序遍历，但你必须记住：在这道题里，遍历顺序不改变结果的正确性。

3.2 队列实现BFS：每处理完一层就计数

BFS的思路更加直观：把根节点放进队列，然后一层一层往外扩展。每处理完一层，深度计数加1，队列里剩下的刚好是下一层的全部节点。

class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } depth++; } return depth; } }

这个模板最核心的一行是int size = queue.size()，必须在循环外先取出来，因为它锁定了当前层的节点数。如果你偷懒写成for (int i = 0; i < queue.size(); i++)，那么在循环体里poll一个节点又offer它的孩子，queue.size()一直在变，for循环的终止条件就会被干扰，表现出来的症状就是深度偶尔多算一两次，或者节点数对不上。

另一个细节是Java里要用List的LinkedList还是ArrayDeque。如果入队的节点存在null值，比如要把null子节点也放进队列来占位，ArrayDeque会直接抛NullPointerException，因为它的实现不允许null元素。这道题我上面的写法是只入队非空子节点，所以用哪个都行，但如果你改写成“空节点也入队”的版本，一定要用LinkedList。

3.3 DFS迭代和BFS的空间取舍怎么选

两种迭代方法的操作数量都是O(n)，差别全在空间上。DFS迭代的栈深度等于树高，BFS的队列长度等于某一层节点的最大数量。

拿两种极端树形来对比会非常直观。一棵完全二叉树，最后一层节点数大约为n/2，BFS的队列在扫描最后一层之前会膨胀到n/2，空间是O(n)；但它的高度只有O(log n)，DFS迭代栈最多就log n层。反过来，一棵退化成单链的树，高度是n，DFS迭代栈深度是O(n)，而BFS队列每层最多就1个节点，空间是O(1)。

所以如果你只知道树很“瘦”，优先用BFS省空间；如果树很“胖”，DFS迭代更稳。但面试时这个问题没有绝对答案，关键是能把这段分析说给面试官听，让他看到你不是死背代码。

4. 写二叉树老报运行时错误？这份排错清单你收好

4.1 高频报错场景与排查方法

很多人在LeetCode上提交二叉树相关的代码，经常莫名其妙就Runtime Error，点开详情一看，大部分是空指针，或者极少数情况下的栈溢出。我根据自己刷题和帮别人看代码的经验，把最高频的几种问题列成了排查表。

其中空指针占比最高。典型的错误代码长这样：递归函数里先int left = maxDepth(root.left)，然后才判断root是否null。这意味着当你递归到叶子节点的下一层时，root已经是null，对null取.left直接炸。通过现在的报错堆栈定位到那一行，马上就能发现问题。

4.2 提交前必跑的最小用例集

二叉树题目的测试用例很有规律，我建议无论题目要求多简单，本地都要先跑完这几类用例再提交。

第一类是空树：root为null，期望输出0。第二类是单节点：一棵只有一个根节点的树，期望输出1。第三类是只有单侧子树：比如根节点只有左孩子，左孩子又有左孩子，期望输出3，这类用例最容易暴露左右深度取max还是取sum的问题。第四类是完全二叉树：[3,9,20,null,null,15,7]这样的标准测试树，期望输出3。第五类是“斜树”即单链，期望值等于节点数，用来测试递归深度和极端情况。

我自己的习惯是本地写一个从数组构建二叉树的辅助方法，把LeetCode页面上的测试样例直接粘贴成数组，然后在自己的main里跑一遍。LeetCode上很多树题目其实都可以共用这套建树辅助方法，一次写好，后面几十题都能用，非常划算。

4.3 面试现场怎么讲这道题才不浪费

这题出现在面试里，通常不是真的只想听你背一个递归，而是想借一个简单问题考察你的表达能力、边界意识和优化意识。我建议的表达顺序是三步走。

第一步，先跟面试官确认边界：空树返回0可以吗？节点数量有没有说上限？这里的深度按节点数算还是按边数算？这几个问题一抛出来，对方就知道你平时写代码会主动澄清需求。

第二步，讲递归思路，同时主动补充复杂度：时间是O(n)，空间是O(height)，height在最坏情况下等于n。然后顺势往下说：“如果树的深度可能很大，递归就会有栈溢出风险，所以我会改成迭代。”

第三步，给出迭代方案。可以先说栈模拟，再说BFS，并对比两种方式的空间差异。最后如果能提到BFS的层序号在算“二叉树最大宽度”这类题里也有用，这场面试的加分项基本就拿到了。写代码时每写完一个核心步骤，拿着刚才确认的边界用例在脑子里走一遍流程。

5. 一道题辐射一片题：平衡二叉树、直径与工程启示

5.1 平衡二叉树：一次后序遍历同时判断高度和平衡性

104题的后序遍历模板，直接套到LeetCode第110题“平衡二叉树”上几乎不用改。判断一棵二叉树是否平衡，本质上就是看每个节点左右子树的高度差是否都不超过1。

如果你先分别算左子树高度和右子树高度，再回判断平衡，会重复遍历很多次。更好用的是在递归返回高度的同时返回一个特殊值表示“此树不平衡”，这样每个节点只遍历一次。

class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; } private int getHeight(TreeNode node) { if (node == null) { return 0; } int leftHeight = getHeight(node.left); if (leftHeight == -1) { return -1; } int rightHeight = getHeight(node.right); if (rightHeight == -1) { return -1; } if (Math.abs(leftHeight - rightHeight) > 1) { return -1; } return Math.max(leftHeight, rightHeight) + 1; } }

你看，getHeight的后半段返回逻辑，跟104题的maxDepth一模一样，区别只在于多了两个提前返回-1的剪枝。这就是为什么我说104题是最值得吃透的模板题，因为它自身简单，但经过两次小改之后就变成了另一个经典题。

5.2 二叉树的直径：深度相加与返回值解耦

第543题“二叉树的直径”看起来和最大深度完全不像，实际上代码也只是微调。二叉树直径的定义是任意两个节点之间路径的最大边数，这条路径不一定要经过根节点，但一定经过某个节点，并且在这个节点处拐弯。

于是可以对每个节点算一个候选值：左子树深度 + 右子树深度，这就是一条经过当前节点、连接左子树某个叶子到右子树某个叶子的边数。全局维护一个最大值即可。但注意，递归的返回值仍然必须是“单边深度”，也就是Math.max(左, 右) + 1，这样才能让父节点继续使用当前节点的深度信息。

class Solution { int maxDiameter = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return maxDiameter; } private int depth(TreeNode node) { if (node == null) { return 0; } int left = depth(node.left); int right = depth(node.right); maxDiameter = Math.max(maxDiameter, left + right); return Math.max(left, right) + 1; } }

如果你已经深刻理解了104题“返回的是单边最大深度”这件事，再看543题就会觉得顺理成章：返回值是给上面用的，额外变量是给最终答案用的，一个函数同时干了两件事。这种“借递归返回子结构信息，同时更新全局答案”的模式，在后面很多二叉树题目里会反复出现。

5.3 N叉树、层序套路与搜索二叉树的工程含义

N叉树的最大深度就是把递归里的左右分支改成遍历子节点列表，代码如下：

class Solution { public int maxDepth(Node root) { if (root == null) { return 0; } int max = 0; for (Node child : root.children) { max = Math.max(max, maxDepth(child)); } return max + 1; } }

思路一点没变，只是子问题从两个变成了若干个。这再次说明104题的核心不是二叉树的“二”字，而是“递归地去算子树的深度”这个分治模型。

再往外走，104题的BFS写法就是102题二叉树层序遍历的骨架，只要在循环里把每层的节点值收集到列表里就变成了层序遍历；二叉树的右视图、填充每个节点的下一个右侧节点指针，也都是在这个BFS模板上加一小段逻辑。

最后说一个容易被人忽略的工程角度。搜索二叉树在理想情况下查找、插入都是O(log n)，而这棵树的“最大深度”其实就是树高。如果一棵搜索二叉树没有自平衡机制，恰好插入顺序是递增的，它就会长成一条单链，深度变成n，查找复杂度直接退化成O(n)。这正是AVL树、红黑树等自平衡搜索树存在的价值。刷一道最大深度之后，如果你能把这个点连起来，对数据结构的理解就完全不一样了。

6. 写在最后：Hot100第28题的一些真实感受

我当年刷这道题的时候，第一版提交的就是最朴素的递归，过了就没再管。后来一次模拟面试被问到“树特别深怎么办”，我卡了一小会儿才答出来可以换迭代BFS，但当时对两种迭代的空间差异也没讲清楚，面试官明显感觉到我是“背解法”而不是“懂解法”。回去之后我把二叉树的递归、栈模拟、层序这几种遍历串起来重新梳理了一遍，再刷平衡二叉树和直径相关的题目时，明显顺了很多。

如果你正在按Hot100的顺序刷，我建议不要只满足于把这题通过。拿它当一个枢纽，把后序遍历模板、BFS层序模板、递归栈深度的危险边界、以及“返回值和全局答案分离”这个手法都过一遍，后面二十来道二叉树相关的Hot100题目会轻松不少。

另外分享一个对我帮助很大的小习惯：在本地维护一个建树工具函数，把LeetCode的数组形式的二叉树用例一键转成TreeNode对象，这样所有树的题都可以在本地打断点调试，而不是在网页上盲猜。把基础题的调试手感练出来之后，你再看那些“为什么总报运行时错误”的帖子，基本一眼就能锁定问题出在哪一类。Hot100刷到28题才走完四分之一，但二叉树的底子打牢了，这一趟就值回票价。