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与BFS3.1 栈模拟DFS节点和深度一起入栈递归有栈溢出的风险那就用迭代来绕开。DFS迭代的一种优雅做法是拿两个栈一个存节点一个存这个节点对应的深度。class Solution { public int maxDepth(TreeNode root) { if (root null) { return 0; } DequeTreeNode nodeStack new ArrayDeque(); DequeInteger 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; } QueueTreeNode 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/2BFS的队列在扫描最后一层之前会膨胀到n/2空间是O(n)但它的高度只有O(log n)DFS迭代栈最多就log n层。反过来一棵退化成单链的树高度是nDFS迭代栈深度是O(n)而BFS队列每层最多就1个节点空间是O(1)。所以如果你只知道树很“瘦”优先用BFS省空间如果树很“胖”DFS迭代更稳。但面试时这个问题没有绝对答案关键是能把这段分析说给面试官听让他看到你不是死背代码。4. 写二叉树老报运行时错误这份排错清单你收好4.1 高频报错场景与排查方法很多人在LeetCode上提交二叉树相关的代码经常莫名其妙就Runtime Error点开详情一看大部分是空指针或者极少数情况下的栈溢出。我根据自己刷题和帮别人看代码的经验把最高频的几种问题列成了排查表。错误现象典型原因排查思路解决方案NullPointerException对null节点调用了.left或.right顺着报错堆栈找到对应行看访问节点前有没有判空进入递归先写if (root null)保护迭代中入队前判空StackOverflowError树高度过大递归层数过深检查树是否退化成单链或者递归终止条件缺失改成栈模拟DFS或BFS答案总是多1或总是少1根节点是否计数没设计好用空树和单节点用例先跑一遍空树返回0单节点返回1自定义用例验证本地IDE能跑提交就编译错方法签名和题目要求不一致检查类名是不是Solution方法是不是public返回对应类型不写main方法不额外声明TreeNode类偶尔答案不对但不是空指针循环内动态调用queue.size()看BFS代码里是否在for循环条件中取size循环外先int size queue.size()其中空指针占比最高。典型的错误代码长这样递归函数里先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题才走完四分之一但二叉树的底子打牢了这一趟就值回票价。