刷题刷到“二叉树的最大深度”这道题的时候很多人会觉得这不就是递归入门题吗确实它在力扣上是第104题属于二叉树经典题也是面试高频题。但真正让我想写一篇详细笔记的原因是很多人在写这道题的时候会遇到一种非常典型的挫败感——代码看着没毛病一提交就报运行时错误或者递归思路背下来了换个迭代写法就卡住。这些我都经历过而且排查过程挺有代表性的。这篇笔记就围绕这道题把递归、迭代、常见报错和延伸应用一次说透帮你把这道“入门题”真正吃成“基础盘”。1. 题目拆解与核心概念1.1 题目本身在问什么力扣104题的描述非常简洁给定一个二叉树找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。注意这里的措辞说的是“节点数”不是“边的条数”。如果一棵树只有一个根节点它的深度是1不是0。这个细微差别会在后面写代码时直接影响返回值初始化很多人在这里栽过跟头。还要区分一个概念树的深度和高度。在大多数教材里深度是从根节点往下数的层数高度是从叶子节点往上数的层数。对于整棵树来说根节点的高度就是整棵树的最大深度二者数值相等所以题目叫“最大深度”本质上可以理解为“这棵树一共有多少层”。1.2 深度计算和遍历是什么关系计算最大深度本质上必须访问树的所有节点因为你永远不知道最深的叶子藏在哪条分支上。这就牵扯到二叉树的遍历方式前序、中序、后序、层序。前序遍历是“根左右”中序遍历是“左根右”后序遍历是“左右根”层序遍历是一层一层往下扫。计算最大深度通常有两种主流思路递归法对应后序遍历先算左右子树深度再取最大值加1迭代法对应层序遍历每遍历一层计数器加1这两种思路分别对应了“分治思想”和“模拟层次”两个角度学好了不仅能解这道题后面遇到“二叉树的最小深度”“二叉树的右视图”“填充每个节点的下一个右侧节点指针”等题目都能复用同一套思维。2. 递归解法从直觉到严谨2.1 递归三要素怎么套用递归解法的代码极其简短但正因为简短很多人是背下来的没有真正理解。递归题从来只有三件事终止条件、返回值、单层逻辑。放在这道题里终止条件当前节点为null深度为0返回值当前节点为根的子树最大深度单层逻辑左右子树深度的较大者加1对应代码就是这样public int maxDepth(TreeNode root) { // 终止条件空节点深度为0 if (root null) { return 0; } // 单层逻辑左子树深度和右子树深度取较大值再算上当前节点这一层 int leftDepth maxDepth(root.left); int rightDepth maxDepth(root.right); return Math.max(leftDepth, rightDepth) 1; }这段代码看起来人畜无害但里面藏着两个关键认知。第一递归函数返回的是“以当前节点为根的子树的最大深度”不是“从根到当前节点的深度”。方向搞反逻辑就会乱。第二加1的那个1是当前节点自己这一层。很多初学的人写成Math.max(leftDepth, rightDepth)不加1结果所有结果都比正确答案小1这种错误特别隐蔽。2.2 两种写法差异在哪网上还有一种更“精简”的写法public int maxDepth(TreeNode root) { return root null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) 1; }这种写法在面试时显得干净利落但如果你还在学习阶段我建议写成第一种展开形式。原因是第一种写法明确拆出了终止条件和左右子树的计算过程方便调试打断点第二种写法的表达式嵌套在一起你很难在中间状态观察左子树和右子树各自算出来的深度。面试时用哪种都行但平时练习多写几步能帮你建立递归的“展开图景”。这里推荐一个非常有用的调试技巧在IDE里对递归函数加断点观察调用栈的变化。你会看到栈从根节点一路压到最左叶子然后逐层弹出再去右子树压栈。这个过程看一次比默写一百遍都管用。2.3 时间复杂度与空间复杂度分析递归解法的时间复杂度是O(n)因为每个节点恰好被访问一次。空间复杂度是O(height)height是树的高度因为递归调用栈的最大深度恰好是树的高度。极端情况下完全二叉树高度约log2(n)空间复杂度O(log n)链状树每个节点只有一个孩子高度等于n空间复杂度O(n)链状树这条很多人在分析时会漏掉。面试官如果追问“最坏情况下空间复杂度是多少”答O(n)才是对的。这也直接关系到一个常见的提交报错递归栈溢出Stack Overflow后面我会专门讲。3. 迭代解法层序遍历与DFS双栈3.1 为什么还要学迭代写法递归写法如此简洁有些人会产生疑问那我为什么要学迭代“只写递归不写迭代”在面试中基本上是不够的尤其是当树的深度特别大时递归会导致调用栈溢出而迭代法用的是显式的栈或队列只要内存足够就能扛住更深的树。另外很多经典题目比如“二叉树的层序遍历”“二叉树的最大宽度”天然适合迭代思路打好了底子后面刷题会顺很多。层次遍历的思路是用队列逐层存放节点每弹出完一层计数器加1。这就相当于拿一把尺子从上往下量树的层数量一层记一笔。3.2 BFS层序遍历代码实现使用队列实现层序遍历Java里推荐用ArrayDeque而不是LinkedList作为队列实现因为ArrayDeque在频繁入队出队时性能更好而且不允许null元素能避免一些奇奇怪怪的空指针问题。public int maxDepth(TreeNode root) { if (root null) { return 0; } DequeTreeNode queue new ArrayDeque(); 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); } } // 一层处理完毕深度加1 depth; } return depth; }这里有个非常关键的细节int size queue.size();必须放在for循环之前固定下来。如果直接在循环条件里写i queue.size()由于循环体内部不断有子节点入队queue.size()会动态变化导致一轮循环把下一层的节点也弹出去了计算结果就会出错。这个问题在“二叉树的层序遍历”题目中也出现过属于刷二叉树题里特别经典的一个坑。3.3 DFS双栈写法另一种迭代思路除了层序遍历还有另一种迭代思路用栈模拟递归的过程。递归用到的是系统调用栈那我们用显式栈也能达到同样效果。这种写法的核心是栈里不仅要存节点还要存这个节点对应的深度。Java里没有像C的pair可以用一个简单的内部类或者两个平行栈来实现。这里展示双栈写法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(); Integer curDepth depthStack.pop(); maxDepth Math.max(maxDepth, curDepth); // 先压右子节点再压左子节点出栈顺序不影响最大深度计算 if (node.right ! null) { nodeStack.push(node.right); depthStack.push(curDepth 1); } if (node.left ! null) { nodeStack.push(node.left); depthStack.push(curDepth 1); } } return maxDepth; }这种写法可能比你想象中更“笨”但它深刻展示了递归和迭代其实是一体两面递归隐式地用系统栈保存了每一层的状态迭代则是把这些状态显式地放在了自己的栈里。当你理解了这层关系再回头看递归代码就不会觉得它是什么玄学了。4. 为什么总报运行时错误排查实录4.1 空指针异常的根源在哪结合很多刷题者的高频吐槽——“写二叉树程序时为什么总是报运行时错误”我可以负责任地说这道题80%的运行时错误来自两行代码的缺失if (root null) { return 0; }很多人在写递归时想着“反正树不为空”但递归一直向下走总会遇到叶子节点的左右孩子那些孩子就是null。如果不判空直接访问root.left或root.right立刻抛NullPointerException。力扣的报错信息是“java.lang.NullPointerException”位于maxDepth方法内某一行很多人盯着那行代码看半天也看不出问题其实问题出在递归的下一层。调试建议在递归函数第一行加一个日志输出打印当前节点值和是否为空。你会看到程序一路打印到某个叶子节点的null孩子然后崩掉。真相大白。4.2 递归栈溢出不是闹着玩的另一种运行时错误是StackOverflowError。出现这种错误通常不是你的代码写错了而是测试数据里有一棵特别深的树。有些二叉树题目为了测试边界情况会构造一条长达几万个节点的链式树。此时递归深度达到几万层Java默认的线程栈根本扛不住直接爆栈。怎么解决改成迭代写法用显式栈或队列如果真的想坚持递归则可以把递归转换成尾递归但Java对尾递归没有优化所以意义不大面试时可以先说出递归写法再补充说明“如果树的深度非常大我会改成迭代法避免栈溢出”这反而是一个加分项4.3 迭代写法里的隐藏陷阱层序遍历虽然避免了递归栈溢出但也有自己的坑。比如忘记固定size queue.size()导致一层内混入多层节点使用LinkedList作为队列却调用push/pop方法把队列当成栈用在遍历过程中修改了树的节点引用导致死循环第三个坑藏在很多“看起来正确的代码”里。有一种扩展写法是先交换左右子树再递归求深度如果在交换后没有正确区分“已处理的层”和“待处理的层”队列就会永远不为空程序死循环。这种问题在力扣上不会超时而是报“Time Limit Exceeded”遇到时要优先怀疑是不是循环条件出了问题。4.4 常见问题速查表报错或错误现象可能原因解决方案NullPointerException递归未判空访问了null节点的孩子在递归函数起始处增加空节点判断StackOverflowError树深度过大递归调用栈溢出改用迭代法BFS队列或显式栈返回结果少1返回时忘记加当前节点这一层的1检查返回值逻辑max(left, right) 1返回结果多1初始深度误设为1初始深度应为0每处理完一层再自增超时TLE层序遍历未固定size或循环条件导致死循环固定每层节点数量检查队列进出是否正常5. 从这道题延伸出去变体、应用与刷题路线5.1 二叉树最大深度的实际应用场景刷题时很多人会问这东西除了面试到底有什么用我可以告诉你用处还真不小。数据库索引中的B树和红黑树它们的高度直接决定了查询的时间复杂度。一棵平衡的树高度是O(log n)一旦树退化成链表高度变成O(n)查询性能急剧下降。日常开发中如果你的系统用到了树形结构做缓存或路由监控树的深度就是在监控性能退化风险。前端开发中DOM树和组件树都有层级结构。计算某棵子树的最大深度可以辅助判断页面嵌套是否过深从而优化渲染性能。React的Fiber树遍历、Vue的虚拟DOM diff底层都离不开树的遍历和深度计算。文件系统的目录结构也是一棵多叉树递归删除文件夹、统计文件夹总大小、限制目录层级深度这些操作本质上都是树深度计算的应用。5.2 从104题延伸出的变体题这道题的变体特别多而且每一道都能看出你“是否真的吃透了树的深度”110. 平衡二叉树判断左右子树高度差是否不超过1要求逐层自底向上判断核心逻辑就是求左右子树深度111. 二叉树的最小深度注意最小深度是从根到最近叶子节点的节点数不能简单把max改成min因为如果一个子树为空min会错误地取到0222. 完全二叉树的节点个数利用完全二叉树的性质结合深度计算可以做到比O(n)更快559. N 叉树的最大深度把左右孩子改成遍历children列表递归逻辑几乎不变最小深度这道题值得多说两句。很多人以为把Math.max改成Math.min就行了但这样会导致一个错误如果某个节点只有右子树没有左子树左子树深度算出来是0min(0, 右子树深度)1直接变成1显然不对。正确做法是分情况讨论左右子树都非空才取min如果有一侧为空则取另一侧的深度加1。这个坑非常经典我建议刷完104立刻去做111对比着看理解会更深刻。5.3 二叉树遍历的底层思维递归与回溯二叉树问题的底层思维说到底就是递归与回溯。递归的“递”是沿着一条路径深入到叶子递归的“归”是从叶子一层层带着结果返回。回溯则是到达某个节点后尝试所有可能的分支。在最大深度这道题里后序遍历就是一种“回溯”——先深入左子树拿到结果回到根节点再深入右子树拿到结果最后在根节点汇总。理解了这个过程你再去做“路径总和”“二叉树的所有路径”这类回溯题时会有一种豁然开朗的感觉它们共享同一套递归框架只是单层逻辑里做的事情不同。这也是为什么所有二叉树的刷题攻略都会建议先死磕遍历再谈其他。前序、中序、后序、层序这四种遍历方式是二叉树世界的基础动词。104这道题之所以被放在“二叉树热题100”的前列就是因为它虽然没有直接问“遍历”但无论你用哪种解法都必须先把遍历理解透彻。5.4 我的个人刷题路线建议刷二叉树相关题目我的建议路线是先掌握前序、中序、后序、层序的递归写法再掌握前序、中序、后序、层序的迭代写法用104题检验对深度和遍历的理解刷110平衡二叉树、111最小深度、559 N叉树深度做变体巩固再挑战222完全二叉树节点个数、236最近公共祖先、297二叉树序列化按这个顺序走过来你建立的不是一道题的答案而是一整套“树的递归思维框架”。后期刷动态规划里的树形DP比如打家劫舍III、二叉搜索树的各种操作你会发现底层全是这套东西。最后说一点我在实际调试中的体会写二叉树代码时一定要养成“空指针前置判断”的肌肉记忆。每写一个递归函数先写终止条件每访问一个节点的孩子先确认这个节点不为空。这种习惯在刷题阶段是过关机器在工作中写业务代码时更是保命技能——线上服务可没有调试器给你慢慢看调用栈。把104这道题当作一个起点把“先判空、再递归、后回溯”这几个字刻在脑子里你会发现后面所有二叉树题目都顺了。