LeetCode 104二叉树最大深度：递归BFS迭代DFS三种解法与避坑指南

104题大概是LeetCode hot100里最“容易”又最“坑”的一道题了。说它容易是因为题目一句话就能看懂给定一棵二叉树的根节点返回这棵树的最大深度。说它坑是因为很多人在本地IDE里跑得好好的一粘贴到LeetCode上就报运行时错误还有的人代码逻辑看起来完全没问题但提交后就是空指针异常。这个现象在hot100题解区特别常见尤其集中在二叉树的遍历与深度计算这类入门题上。所以这篇文章不止是给一个标准答案我想把“二叉树的最大深度”这题从根上拆透。我们会用递归DFS、迭代BFS、迭代DFS三种思路来实现把每步的返回值、递归终止条件、空间消耗全部讲明白再专门用一章来回应一个高频痛点——“写二叉树程序时为什么总是报运行时错误”把空指针、栈溢出、被测环境差异这些坑挨个排掉。适合刚开始刷hot100的读者、准备面试前想系统地过一遍树形递归的人以及卡在代码运行报错上迟迟想不通的朋友。1. 题目背后在考什么最大深度的本质1.1 先搞清楚二叉树的深度到底怎么定义LeetCode 104的题目原文很简单给你一棵二叉树的根节点 root返回它的最大深度。但“深度”这个词在不同资料里其实是有点小区别的。有的书把根节点的深度定义为0有的定义为1LeetCode这道题采用的是后者从根节点到最远叶子节点的最长路径上的节点数。也就是说空树深度为0只有一个根节点的树深度为1根节点加一个左孩子的树深度为2。这个定义直接影响了递归终止条件的写法。如果根节点深度定义为0那递归返回时处理逻辑会略有不同但核心思想是一致的逐层往下走每走一层深度加1直到遇到空节点。很多人写递归时搞混了“节点数”和“边数”把最大深度写成节点之间的边条数导致结果差1。LeetCode的示例里通常会用 [3,9,20,null,null,15,7] 这样的层序序列来表示树最大深度是3你数节点数就是3数边数则是2。动手写之前先把这个基准对齐后面所有解法才不会跑偏。另一个容易混淆的概念是“深度”与“高度”。在不少中文教材里节点的深度是指从根节点到该节点的边数/层数而节点的高度是指从该节点到最远叶子节点的边数/层数两者方向不同。但LeetCode 104要的是整棵树的最大深度从实现角度看它等价于根节点的高度。所以在讨论这道题时我一般直接说“最大深度就是整棵树的层数也就是根节点到最远叶子节点经过的节点总数”这样最不容易产生歧义。1.2 为什么这题是hot100的“试金石”在hot100题库里二叉树相关题目占了相当大的比例而104基本是很多人刷树的第一站。它看起来简单但背后考查的东西一点不少递归思想是否牢固、对树的遍历是否熟悉、对各种树形态空树、单节点、斜树、满二叉树的边界处理是否谨慎。更重要的是它能测验你对递归调用栈的理解程度。因为最大深度这道题用递归写只要三五行可是这三五行里一旦少写了一个判空分支运行时错误就会立刻蹦出来。面试场景里这题也经常被拿来当“热身题”。面试官会让你手写解法然后追问“如果树特别深递归会不会崩迭代怎么写”这就从一道简单题直接上升到对复杂度和工程思维的考察。我见过不少候选人递归秒过但一问到递归栈的深度最坏是多少就卡壳了。所以这篇博文不只是为了通过104更是为后面刷平衡二叉树、二叉树的直径、路径总和这些hot100题打底。树形递归的“模板感”一旦建立起来后面很多题目都可以套用。1.3 换个角度看最大深度就是层序遍历的层数除了递归我们还可以用另一种直觉来理解最大深度把二叉树想象成一颗洋葱从根节点开始每次剥掉当前最外层的一层节点剥了多少次深度就是多少。这正是层序遍历的思想。用队列做层次遍历时每处理完一层计数器加1等队列全部清空计数器的值就是最大深度。这个视角很有用因为很多新手被递归绕晕后可以用层序遍历来“保底验证”。比如你递归写出了答案但不确定对不对可以再写一个BFS版本跑同一组测试数据两个结果一致基本就稳了。而且BFS版本的额外优势是不会占用系统递归调用栈在树深度很大的情况下不容易栈溢出实际工程里也更适合处理那种极端的“斜树”场景。后面我会详细展开BFS的实现这里先记住一个结论深度既可以用“根到叶的路径节点数”来理解也可以看成“树的层数”两种理解对应两类解法。2. 三种主流解法的选择与原理2.1 递归DFS最短代码背后的信任问题递归是求解最大深度最自然的思路因为问题的结构本身就是递归的一棵二叉树的最大深度等于左子树的最大深度和右子树的最大深度中较大的那个再加1加的是根节点自己。如果用伪代码写就是function maxDepth(node): if node is null: return 0 leftDepth maxDepth(node.left) rightDepth maxDepth(node.right) return max(leftDepth, rightDepth) 1在Java里的实现也很直接public int maxDepth(TreeNode root) { if (root null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; }很多第一次接触的人会问为什么空节点返回0而不是1因为空节点不包含任何节点不该计入深度。而叶子节点的左右孩子都是空叶子节点自身返回的深度是 max(0, 0) 1 1这正好符合“单节点树深度为1”的定义。这个终止条件是整段代码的灵魂漏掉它或写错它程序就会无限递归或者返回错误的深度值。递归DFS之所以让人既爱又恨是因为它把复杂的遍历过程交给了函数调用栈。你在代码里看不到显式的“遍历”动作但每一次递归调用都在隐式地向下探索。这种抽象能力是好事可也意味着你必须充分信任递归的“契约”函数会返回以当前节点为根的子树最大深度。一旦你在写的时候没有想清楚这个契约就很容易在多层的递归里绕晕。我的建议是写这种递归函数前先把注释写上“返回以node为根的子树的最大深度”然后用这个定义去推导代码错误率会低很多。2.2 迭代BFS用队列数清楚每一层如果不想依赖递归BFS是最符合直觉的替代方案。我们用队列把每一层的节点装进去然后一层一层地往外扩。处理完一层深度计数器就加1。整个过程和“剥洋葱”一模一样。from collections import deque def maxDepth(root): if not root: return 0 queue deque([root]) depth 0 while queue: depth 1 level_size len(queue) for _ in range(level_size): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depth这里有一个非常关键的细节必须在进入每一层时先记录level_size len(queue)然后循环处理level_size次。因为队列在循环过程中会不断加入新的节点如果不提前锁定当前层的节点数量就会把下一层的节点也在当前轮次里处理掉导致深度计数错乱。这是层序遍历最常见的一个bug尤其是在处理完左孩子后又把右孩子加进来时很容易头脑发热把for _ in range(len(queue))直接写进循环条件里。BFS的空间复杂度在最坏情况下是O(n)因为队列中最多会同时存在一整层的节点。对于完全二叉树来说最后一层可能有 n/2 个节点所以空间占据上是线性的。优点是它不会因为树的深度过大而栈溢出因为用的是堆内存里的队列而不是操作系统线程栈。在普通实现里BFS代码比递归稍长但胜在逻辑直观而且这个“按层处理”的框架后面还能直接套用到“二叉树的最大宽度”等题目里。2.3 迭代DFS用栈手动维护“当前深度”BFS用队列天然匹配“层”的概念DFS则可以用栈来模拟递归过程。既然递归本身就是在系统栈上压栈弹栈那我们完全可以在堆上自己创建一个栈把“当前节点”和“走到当前节点时的深度”一起压进去。每次从栈里弹出一个元素时就用它的深度更新最大深度然后把它不为空的左右孩子压进栈孩子的深度是当前深度加1。def maxDepth(root): if not root: return 0 stack [(root, 1)] max_depth 0 while stack: node, depth stack.pop() max_depth max(max_depth, depth) if node.left: stack.append((node.left, depth 1)) if node.right: stack.append((node.right, depth 1)) return max_depth这种写法其实是在模仿递归中的“先访问根再访问孩子”的前序遍历框架。因为栈是先进后出所以压栈顺序不影响最终最大深度的正确性左右孩子谁先谁后都行反正所有节点都会被访问到每个节点记录的是“从根到它自己的深度”。栈中需要同时保存节点和深度信息所以空间复杂度同样是O(n)。相比递归它的优势是不受系统递归调用栈的限制在极端深度的斜树上也不会抛StackOverflowError。还有一些人会写“后序迭代法”用一个栈模拟递归的完整调用流程最后弹栈时再更新深度。那样做更贴近编译器递归执行的内部原理但代码会复杂很多。对于这道题直接存二元组的方案最简单可靠。我们学习迭代DFS重点不是背代码而是理解“栈加状态”这个通用技巧很多树相关的非递归遍历题都要靠它。2.4 三种方法复杂度和适用场景对比做个直观的对比表格方便你面试时快速回答解法时间复杂度空间复杂度核心机制适用场景递归DFSO(n)最坏O(n)平均O(log n)系统调用栈代码最简洁适合理解递归思想面试首选迭代BFSO(n)最坏O(n)队列按层处理逻辑直观适合需要知道“每一层信息”的变体题迭代DFSO(n)最坏O(n)栈保存节点和深度避免系统栈溢出的场景适合深度很大的树时间复杂度都是O(n)因为每个节点都需要被访问一次。空间复杂度的差别主要在“最坏情况”。递归解法在树退化成链表时递归深度等于节点数量系统栈会消耗O(n)的内存如果n达到十万级可能直接栈溢出。BFS和迭代DFS用的是堆内存中的队列/栈同样最坏需要O(n)空间但一般不容易触发“调用栈内存不足”这种运行时错误。这里还要强调一下很多人说平衡二叉树的空间复杂度是O(log n)这其实是把“树高与节点数的关系”带进来了。对于平衡树高度是log n量级递归栈深度也就是O(log n)。但这不是算法本身的固定复杂度而是取决于输入树的形状。所以在回答面试题时最好先给最坏情况O(n)再补充说“如果输入是平衡二叉树递归栈深度会小很多”。这样既严谨又能展示你的分析能力。3. 实操过程从零写出不报错的题解3.1 先想清楚递归函数的入参和返回值我刷题的习惯是拿到题先不急着写代码先把“这个递归函数到底要做什么”写在注释里。对104题我会写/** * 计算以 node 为根节点的子树的最大深度。 * 如果 node 为空返回 0。 * 否则返回 max(左子树最大深度, 右子树最大深度) 1。 */ private int dfs(TreeNode node) { // ... }明确了入参和返回值之后代码几乎是被“逼”出来的先写终止条件if (node null) return 0;再写递归调用和聚合逻辑。整个过程不超过两分钟。很多人在LeetCode上敲代码时喜欢直接开始写if (root.left ! null)这种显式判空反而把简单问题复杂化了。使用递归的优雅之处就在于每次都只关心当前节点和它的左右孩子不需要在当前这一层去判断孙子节点是否存在——那是下一层递归要做的事情。但有一类错误就是从这里来的如果在递归函数内部你总是先判断node.left ! null再递归那你必须同时处理“node本身为空”的情况。最常见的“运行时错误”是忘了最外层的空树判断或者在某一层递归中访问了null.left。记住递归的首要任务是把空节点的返回条件写好而不是在每个地方都加判空。每个递归调用进来第一行永远是检查当前节点是否为空。3.2 本地调试代码准备别在LeetCode里裸奔初学者很喜欢直接在LeetCode网页上的代码编辑器里写代码写完立刻点提交。这种效率当然高但也很容易因为一个低级错误反复试错。我建议本地IDE里准备一套能直接跑起来的Java或Python模板先在本地调试确认无误后再搬到LeetCode。Java版本需要一个简单的TreeNode类和main方法做测试public class Solution { public int maxDepth(TreeNode root) { if (root null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } } public static void main(String[] args) { Solution solution new Solution(); // 构造一棵树: [3,9,20,null,null,15,7] TreeNode root new TreeNode(3); root.left new TreeNode(9); root.right new TreeNode(20); root.right.left new TreeNode(15); root.right.right new TreeNode(7); System.out.println(solution.maxDepth(root)); // 期望输出 3 System.out.println(solution.maxDepth(null)); // 期望输出 0 } }LeetCode环境本身就内置了TreeNode类所以提交时你只需要粘贴Solution类里的maxDepth方法不用贴TreeNode定义。这是很多人第一次提交报错的原因之一把本地用的TreeNode定义也粘贴上去了导致类重复定义或者编译失败。建议在本地调试时把方法单独放在一个类里提交时只提交那个方法。3.3 测试用例与预期结果把边界情况喂饱这一道题测试用例不多但边界情况必须齐全。我每次写二叉树题目都会建立一套固定的用例集合用例描述层序表示预期最大深度空树null0单节点[1]1左斜树[1,2,null]2右斜树[1,null,2]2完全二叉树[3,9,20,null,null,15,7]3更深的不平衡树[1,2,3,4,null,null,5]3为什么一定要测空树和斜树空树测的是终止条件是否写对了斜树测的是递归深度是否能正确累积同时也能提醒你如果树节点数很多递归是否可能栈溢出。我用递归版答案跑这些用例前几个都很顺利但当我用本地循环生成一个10000层斜树去测的时候Java直接抛出了StackOverflowError。这正是面试官爱追问的点递归不是银弹极端数据下会崩。BFS和迭代DFS版本在处理10000层斜树时则没有任何问题。这不是说递归写法有问题只是我们需要知道每个答案的边界在哪。如果你在LeetCode上只跑官方给的测试用例可能永远不会触发栈溢出因为官方用例不会刻意构造超深树但如果你额外去力扣的测试集边缘试探或者自己拿大型数据测就能暴露问题。刷题不能只求“通过了”要有意识地验证自己的算法在极端输入的鲁棒性。3.4 复杂度计算的完整推导访问每个节点恰好一次所以时间复杂度是O(n)其中n是二叉树节点数。递归的空间复杂度计算要分两步看每一帧调用需要常数级内存递归的最大深度等于树的高度h所以空间复杂度是O(h)。在最坏情况下树退化成一个链表h等于n也就是O(n)在最好/平均情况下如果是平衡二叉树h约等于log n也就是O(log n)。BFS的空间复杂度是队列中最多同时存储的节点数也就是树的最大宽度。完全二叉树最后一层大约有n/2个节点所以最坏也是O(n)。迭代DFS的栈中最多存储的节点数量同样和树的形态有关最坏情况下斜树会一直把右孩子压栈栈中保存的节点数量也是O(n)。这三个方案的时间复杂度一模一样空间复杂度的最坏情况也都是O(n)所以在LeetCode判题结果上三者通常都会通过速度差异很小。此时选择哪种写法主要看你更想展示递归思想还是更想证明自己掌握了迭代写法。我还经常被问到“能不能做到更快”。答案是找最大深度必须看完整棵树至少访问一次所有节点所以O(n)已经是最优时间复杂度。如果有人非要说“剪枝优化”那是针对特定问题形态的比如找“最浅深度”时可以在遇到叶子节点后提前终止找“最大深度”的时候任何节点都可能通向更深的路径剪不掉。4. 常见问题写二叉树程序为什么总是报运行时错误4.1 运行时错误第一号空指针访问在LeetCode上104题最常见的运行时错误就是java.lang.NullPointerExceptionPython 则是AttributeError: NoneType object has no attribute left。原因基本一致递归到空节点时代码仍然尝试访问它的左右孩子。我见过一个典型的错误写法public int maxDepth(TreeNode root) { if (root.left null root.right null) { return 1; } return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; }这段代码在root为叶子节点时没问题但如果root本身就是null第一行root.left就直接空指针了。就算root不为空只要某一层的某个孩子为null递归调用时也会在root.left那里崩溃。这类问题的根源是“先访问再判空”和“递归终止条件只覆盖叶子节点没覆盖空节点”。解决思路非常简单把终止条件统一成if (root null) return 0;。这样一来叶子节点的左右孩子会被递归调用但进入空节点后直接返回0就不会再有任何空指针访问。这个调法能让所有后续对root.left或root.right的访问都发生在“当前节点非空”的上下文里从根上杜绝了空指针。4.2 运行时错误第二号递归没有出口导致栈溢出如果你遇到的是StackOverflowError说明递归一直在无节制地压栈。常见的原因有两个。第一是没有写终止条件或者终止条件永远不成立比如if (root null) return 1;这种写错返回值的也会导致逻辑异常但栈溢出主要来自缺失有效的递归出口。第二是输入树本身深度过大比如节点数达到几万甚至几十万而递归深度就是节点数Java线程栈默认大小通常只有512KB到1MB每帧至少占用几十字节递归个几万层就撑爆了。这种问题在LeetCode上不一定常见因为官方测试用例的树深度通常控制在一个合理范围内。但你在本地自测时很容易自己构造一个大斜树然后疯狂报错。要区分是代码问题还是输入问题可以先把递归版在斜树上测一测如果100层能跑1万层就崩那么代码逻辑多半没问题是系统栈的限制。如果真的需要处理超深树就改用BFS或迭代DFS。我还遇到过一些人把递归函数写在main函数里用局部类超多导致每次递归都会创建新对象也加剧了内存开销但这种属于写法太绕不推荐。4.3 运行时错误第三号本地能跑LeetCode却报错这一条是最让人摸不着头脑的。本地IDE里明明能运行粘贴到LeetCode后却编译失败或执行出错。通常逃不开几种原因本地类名是Main或者任意类名但LeetCode要求提交的类必须是Solution方法签名必须和题目一致。本地把TreeNode类又定义了一遍LeetCode已经内置了TreeNode重复定义直接编译失败。本地用了package包声明提交时没有去掉导致编译错误。本地代码里带了public static void main方法虽然LeetCode允许但有时候多余代码会干扰阅读提交前最好删掉只留核心方法。此外注意主方法签名里的参数类型是TreeNode不是Node也不是自定义的内部类。力扣做题时顶部通常已经有Definition for a binary tree node.注释块里面定义了TreeNode。你只需要实现Solution类中的方法不要修改题目给的TreeNode定义更不要写一个同名的TreeNode类。4.4 排查技巧速查表报错关键信息大概率原因解决方案NullPointerException/AttributeError对空节点访问属性递归第一行加上空节点返回0StackOverflowError递归无出口或树深过大检查终止条件改用迭代BFS/DFSCompile Error类名/方法签名不对或重复定义TreeNode确保类名为Solution删掉自定义TreeNode输出结果为1或总是少1深度定义理解错误用“节点数”而非“边数”计算BFS结果不对每层循环用了变化的len(queue)进入循环前先n len(queue)4.5 一个高级坑全局变量在多测试用例之间污染有些读者不喜欢写递归返回值而是用一个全局变量记录最大深度。比如在maxDepth方法里先定义一个int maxDepth 0;但这是局部变量没问题。问题出在把maxDepth定义成Solution类的成员变量public class Solution { private int max 0; public int maxDepth(TreeNode root) { traverse(root, 1); return max; } private void traverse(TreeNode node, int depth) { if (node null) return; max Math.max(max, depth); traverse(node.left, depth 1); traverse(node.right, depth 1); } }这个代码在单个测试用例里是对的但LeetCode执行测试时不会为每个例子重新创建Solution对象有时候会复用同一个实例跑多个用例。如果max没有在方法开头重置第二个用例的结果就可能残留第一个用例的值导致答案偏大。正确做法是在maxDepth方法内部先用局部变量初始化或者传入一个“当前记录最大值”的引用或者干脆像最简递归那样直接用返回值累加。我个人的习惯是树的递归题优先用“返回值”传递状态而不是用成员变量这样更不容易踩到多用例污染。5. 从最大深度延伸出去的二叉树体系5.1 最大深度与各种遍历方式的关系很多人在刷hot100时会看到“二叉树的遍历”这类热词。坦白说最大深度这道题并不要求你会写中序遍历但如果你想彻底掌握树形题目必须理解深度计算和各种遍历的关系。前序遍历非常适合递归计算深度访问当前节点时深度就已经到了某个值然后往下传。中序遍历也能算出深度但中序的“访问顺序”不是按层来推进的计算深度时需要额外记录当前层数反而别扭。后序遍历则是最自然的递归方案先算左子树深度再算右子树深度最后综合出当前节点深度——104题解法本质就是后序思想的体现。层序遍历和BFS正相关前面已经详细写过。你还会发现前序、中序、后序、层序都绕不开“每个节点都要访问”的约束所以在复杂度上所有解法都是O(n)。真正不同只是“访问顺序”和“状态传递方式”。理解了这个你在面对更多二叉树题目时就不会再纠结“用哪种遍历”而是会想“这道题需要什么顺序的信息”比如判断对称二叉树需要同时比较左右子树对应位置而计算直径需要后序遍历先拿到左右子树的高度。5.2 相关hot100题目与变体清单最大深度的代码模板稍微改一改就能解不少hot100题。最典型的是“平衡二叉树”题思路是把104的递归结果应用到每个节点上判断左右子树深度差是否超过1“二叉树直径”题则是在后序遍历时同时维护一个全局最大值记录的其实是左子树深度加右子树深度“路径总和”题是判断是否存在从根到叶子路径的和等于目标值它的递归终止条件会用到“叶子节点”的判断比“空节点”判断更复杂一档。我把这些变体列出来不是让大家现在就去刷而是想说104是树形递归的最小可用模型。你把这个模型的“递归返回值”和“全局更新”两条线索理清了后面遇到任何需要“自底向上收集子树信息”的题目都能迅速找到思路。比如“打家劫舍 III”这类树形DP本质上也是递归返回两个状态再合并计算套路和求最大深度非常接近。5.3 动态规划视角二叉树上的“递推思想”hot100热搜词里有“hot100动态规划”很多人会觉得二叉树和动态规划是两回事其实它们是相通的。最大深度的递归公式可以写成f(node) max(f(node.left), f(node.right)) 1这本身就是一种状态转移方程只不过是在树形结构上做自底向上的递推。动态规划里的“自顶向下带备忘录”对应递归加缓存“自底向上填表”对应后序遍历把子结果返回给父节点。当然求最大深度用不上缓存因为每个节点只被访问一次没有重叠子问题。但真正的树形DP比如“二叉树中的最大路径和”“监控二叉树”这类hot100延伸题就是在这个递归框架上增加更多状态变量。所以我推荐刷题时把这个最简单的递推想清楚问题能不能分解成规模更小的子问题子问题的解如何合并边界是什么这三个问题想明白树形动态规划的大门就打开了。5.4 搜索二叉树、线索二叉树中深度概念的分量热搜词里还有“搜索二叉树”和“线索二叉树”。二叉搜索树BST的操作复杂度与树的高度直接挂钩一棵平衡BST的查找、插入、删除都是O(log n)一旦退化成斜树就变成O(n)。理解104这道题会帮助你意识到为什么平衡树那么重要——高度就是生命线。AVL树和红黑树的核心工作就是通过旋转把树的高度控制在O(log n)以内从而保证效率。线索二叉树则是把空闲的左右孩子指针利用起来指向遍历序列的前驱和后继这样遍历就不需要递归或栈了。但这个设计并没有改变树的深度结构问题树依然可能很斜线索化只是让“寻找下一个遍历节点”变快了并没有让树变矮。从这个延伸来看深度的概念贯穿了几乎所有二叉树体系无论是优化查找性能还是简化遍历流程最终都要回到“这棵树有多高”这个根本问题上来。所以把104题弄扎实等于给整棵“二叉树知识树”打了地基。写到这里我不禁想起自己第一次刷104时的状态三行代码写完提交报错再看一眼原来是忘了空树返回0。后来陆陆续续把BFS、迭代DFS都写完再把直径题、平衡树题刷透才发现这道“简单题”里的门道其实足够消化一整周。我现在写任何二叉树递归题第一行永远是判空永远先想清楚“这个函数返回什么”这两个习惯就是从104题的坑里养出来的。希望这篇文章能让你少走一点弯路也希望大家在面对“二叉树的最大深度”时不只是记住答案而是真正理解它背后的递归、遍历与边界。