讲递归和二叉树最大深度这个话题之前先说说我自己的经历。前些年带团队面试候选人十个里八个写的都是这个版本的代码public int maxDepth(TreeNode root) { if (root null) return 0; return 1 Math.max(maxDepth(root.left), maxDepth(root.right)); }代码短、逻辑清晰、运行也对但真到追问环节能把这个函数讲透的人不超过三成。很多人只会背模板却说不出递归到底在做什么更回答不了“如果树有十万层怎么办”“为什么这里不用遍历框架”“报空指针异常到底错在哪”。这篇文章就把递归求解二叉树最大深度这件事拆开揉碎从思路到实现从报错排查到题目延伸一次讲清楚。适合刚接触二叉树和递归的初学者也适合准备面试但总在细节上翻车的老手。1. 递归解法的核心思路为什么树和递归这么搭1.1 先写出口再写主逻辑先把问题定义清楚一棵二叉树的最大深度就是从根节点到最远叶子节点的路径上经过的节点总数。空树深度为0只有一个根节点的树深度为1。这个概念看起来简单但写代码时容易出事因为很多人直接跳到“怎么递归”忘了还有空树这个边界情况。递归解决树形问题的套路其实非常固定总共就三步第一步明确递归函数接收什么参数、返回什么结果第二步找到递归终止条件也就是最简单的那个输入第三步假设子问题已经解决把当前问题和子问题的关系写成表达式。拿最大深度来说maxDepth(root)接收一棵树的根节点返回这棵树的深度终止条件是root null时返回0主逻辑就是当前节点的深度等于左右子树深度较大者加1。这个“假设子问题已经解决”的说法初看有点抽象。我换个说法你不需要真的去想递归调用在底层怎么一层层展开你只需要相信maxDepth(root.left)就是左子树的深度maxDepth(root.right)就是右子树的深度然后当前节点把它们接起来。这也叫“递归信任”——把递归函数当作一个已经写好的黑盒只关注当前这一层要做什么。1.2 自底向上的视角把返回值交给上层很多人在这一步卡住是因为脑子里总在想“递归到底怎么倒回去的”。我建议你换个视角递归的本质是从底向上传递信息。拿一棵三层的满二叉树举例1 / \ 2 3 / \ 4 5调用maxDepth(root)后会发生什么系统先把当前状态压入调用栈然后去调用maxDepth(root.left)也就是以节点2为根的那棵子树节点2又会去调用节点4和节点5节点4的左右孩子都是nullmaxDepth(null)返回0所以节点4这一层得到1 max(0, 0) 1。同理节点5返回1。节点2拿到左右子树的结果后返回1 max(1, 1) 2。最后根节点拿到左子树返回的2和右子树返回的1得到1 max(2, 1) 3。你会发现真正“算数”的动作发生在递归返回的路上也就是后序位置。每个节点都不需要知道整棵树的形状它只需要知道自己的左右子树有多高。这种“积累返回值给上层”的模式就是自底向上动态规划在树上的最简单形态。顺便说一句这句话也是很多面试官希望你现场说出来的最大深度问题本质上是在做后序遍历因为在返回阶段才需要用到左右子树的结果。你要是能主动点出这层关系再加一句“如果改成自顶向下就需要在递归时携带深度参数”那这道题基本就稳了。2. 从递归到非递归BFS与栈模拟2.1 层次遍历的天然计数递归解法虽然简洁但它不是银弹。最直接的问题就是当树的高度非常大时递归调用会层层压栈最终抛出StackOverflowError。真实业务里你遇到的不一定是面试题里的漂亮平衡树可能是从数据库里查出来的一棵组织架构树深度几百上千都很常见。这时候非递归解法就成了必需品。最大深度用广度优先搜索BFS来做直觉上就非常顺深度就是层数二叉树的层数就是最大深度。你只需要按层遍历每处理完一层就把计数加1直到队列为空。Java实现长这样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; }这个for循环是精髓。它利用size queue.size()在进入循环前先固定当前层的节点数这样处理完这一层后队列里剩下的就是下一层的全部节点。如果你写成while (!queue.isEmpty())直接 poll那就不是在按层计数而是在数总节点数返回的结果就全错了。这是我见过最多的写错方式没有之一。BFS 的时间复杂度同样是 O(n)空间复杂度是 O(w)w 是树的最大宽度。对于一颗完全二叉树来说最后一层大概有 n/2 个节点所以空间占用在满二叉树场景下会更大一些但对于斜树来说队列里最多同时只有一个节点非常省。2.2 栈模拟带状态遍历如果既想保持非递归又想模拟递归那种“带着当前路径深度一直往下钻”的过程可以用栈来做深度优先搜索DFS。核心思路是栈里存的不是一个节点而是一个“节点 当前深度”的组合。每弹出栈顶就尝试推入它的左右孩子并把深度加1同时维护一个全局最大值。public int maxDepth(TreeNode root) { if (root null) return 0; DequeObject[] stack new ArrayDeque(); stack.push(new Object[]{root, 1}); int maxDepth 0; while (!stack.isEmpty()) { Object[] pair stack.pop(); TreeNode node (TreeNode) pair[0]; int depth (Integer) pair[1]; maxDepth Math.max(maxDepth, depth); if (node.left ! null) stack.push(new Object[]{node.left, depth 1}); if (node.right ! null) stack.push(new Object[]{node.right, depth 1}); } return maxDepth; }这种方案理解起来也不难你把它想象成拿着一份“路线图”在走迷宫每到一个新路口就把“从这里出发的备选路径”压进栈里先沿着当前路线走到头然后回来换下一条。这里的深度就是每条路线已经走过的节点数最大值自然就是最优解。说到递归转非递归你可以顺便练习一个经典类比快速排序的递归版本只要递归区间还有未排序部分就会递归处理左右两个子区间非递归版本则是用一个栈保存每个待处理区间的左右边界循环弹出处理。这两件事的处理思路一模一样都是“把递归函数的调用上下文显式地保存到栈里”。学会了这个迁移不光是二叉树任何递归算法你都能找到对应的迭代版本。3. 运行时错误排查实录把这些坑提前踩平3.1 空指针异常百分之八十的运行时错误都是这个写二叉树程序时最容易遇到的运行时错误是什么答案非常一致NullPointerException。其中最经典的翻车写法是一开始就判断if (root.left null root.right null) return 1;然后主逻辑里直接访问root.left和root.right。乍一看很合理但遇到只有左子树、没有右子树的时候递归调用maxDepth(root.right)传入 null下次进函数先执行root.left直接空指针。正确做法就一条递归函数第一行永远先判空。让空节点返回0把空指针挡在函数门外。这也是为什么很多老手写这个题目时会强调root null的出口放到所有逻辑之前而不是在调用方去判断孩子是否为null。我还见过一种更隐蔽的空指针在层序遍历里用node.left.val而不先判node.left是否为 null。这个场景常见于“把数组层序反序列化构建二叉树”的题目中数组里有null占位构建出来的树有残缺遍历时没判空就会炸。排查办法很简单看异常堆栈指向的源码行八成是对某个对象的字段做了访问前面却没有null判断。3.2 栈溢出递归深度超过虚拟机限制StackOverflowError是另一个高频问题尤其当题目里的二叉树不是平衡树而是退化成了一条链。比如每个节点都只有右孩子树高等于节点数递归深度就是十几万层Java虚拟机默认的栈深度一般在几百到几千层之间很快就爆。这类错误光看代码很难发现因为逻辑完全正确跑小数据也不报错一上大数据就崩。排查思路有三步。第一步看异常堆栈找以java.lang.StackOverflowError开头的错误确认是栈溢出而不是普通的空指针。第二步检查树的高度你可以临时写一个单独计算树高的递归函数如果高度确实过大基本上就能判断是递归深度问题。第三步换成 BFS 或者显式栈的 DFS问题立刻消失。这里给一个我个人的习惯除非确定树高可控否则生产代码里我只用迭代解法。面试时可以用递归展示思路但聊到扩展性时一定要主动提非递归方案。考官想听的往往不是你背得多熟而是你有没有这个风险意识。3.3 递归出口和统计逻辑混写还有一种日志不看仔细根本找不到的问题代码逻辑没问题结果却一直比预期大1。典型的错误写法是public int maxDepth(TreeNode root) { if (root null) return 1; // 错误空树返回了1 return 1 Math.max(maxDepth(root.left), maxDepth(root.right)); }把递归出口的返回值从0写成1就会导致每个节点都多算一层空树直接返回1而不是0。这种错在本地小数据上极难发现因为单节点树返回2看起来好像“也没差多少”直到你用空树或者深度较浅的树做单元测试才暴露。我建议在自测用例中一定要包含空树、单节点、满二叉树、斜树、随机树这五类输入把这五类全部跑一遍再小的逻辑偏差都能暴露。我把这类运行时错误整理成了速查表方便你对照处理异常类型典型触发场景排查方向修复方案NullPointerException递归入口没有判空或在遍历孩子时不判空查看堆栈行号寻找字段访问前的null统一在函数开头判断root null返回0StackOverflowError树高过大递归压栈过深检查树是否退化成链确认递归深度改用BFS或显式栈模拟DFS结果恒定多1空树返回1或递归合并逻辑多加了一次用单节点和空树做边界测试把终止条件的返回值校准为0ClassCastException从Object[]取元素时强转错误检查压栈时存的是什么类型使用Pair或自定义内部类保存节点和深度4. 一道题带出一串题深度问题在二叉树家族里的位置4.1 遍历框架与深度参数最大深度不是孤立的题目它其实站在二叉树遍历框架的枢纽位置上。前面说过递归版最大深度利用的是后序位置——先拿到左右子树的结果再决定当前层的返回值。但你可以在前序位置做同样的事递归时给每个节点携带一个depth参数进入下一层就depth 1然后更新全局最大值。这种自顶向下的写法也很有用尤其当问题需要“对每个节点做一次判断”时比如判断一棵树是不是平衡二叉树。平衡二叉树的定义是左右子树高度差不超过1最直观的做法是对每个节点都调用一次maxDepth计算左右子树高度然后递归检查每个子树是否平衡。这个方法时间复杂度是 O(n log n)因为每个节点都要往下统计子树高度但思路特别直观非常适合作为第一版实现。4.2 平衡二叉树和直径问题从最大深度再往前走一步就到了“二叉树直径”问题。直径的定义是任意两个节点之间的最长路径长度这个路径不一定经过根节点。你可能以为直径就是左子树深度加右子树深度但考过的人都知道直径可能完全落在某棵子树的内部。所以正确的解法是后序遍历中对每个节点用leftDepth rightDepth更新全局最大直径同时返回该节点的最大深度给父节点使用。看到没有这里“返回子树的深度”和“更新全局答案”是两件并行的事。你只要把最大深度那道题的返回值利用好再加上一个max全局变量直径问题就迎刃而解。这也是为什么我一直强调最大深度绝对不只是背一道模板题而是你在理解“能算多少信息并往上传递”的最小单元。深度、高度、层数、路径长度全是从这个单元演化出去的。4.3 搜索二叉树与线索二叉树的延伸再往远看搜索二叉树BST和线索二叉树也和深度、遍历强相关。判断一棵树是否是搜索二叉树有个经典的递归写法对每个节点传入一个允许的取值范围(min, max)递归左子树时更新上界为当前节点值递归右子树时更新下界为当前节点值。这个思路和最大深度的“返回子结果给父节点”在设计上同构都是通过递归约定子问题边界。另一种更取巧的做法是中序遍历后检查序列是否递增因为搜索二叉树的中序遍历天然有序。这两种方案一个自顶向下一个自底向上刚好能帮你把递归的两种视角串起来。线索二叉树则解决的是另一个维度的痛点普通遍历需要栈或者额外空间记录后继节点线索化通过把空指针改造成指向前驱/后继的线索让遍历空间降到 O(1)。有一种叫 Morris 遍历的算法不需要额外空间就能完成中序和前序遍历原理就是在遍历过程中临时修改树的右指针构造出“线索”。所以当你看到“最大深度不需要额外空间、不能递归”这类进阶要求时思路也能往这个方向拓展——只是实践复杂度高不少普通面试不会要求你手写但了解它有助于你理解为什么遍历和深度问题本质上都在处理“怎么高效地走完整棵树”。顺带说一句二叉树的遍历本身就是深度问题的亲戚。层序遍历天然按层输出每层恰好对应一个深度值前序遍历天然适合解题思路是“自上而下处理”的题目后序遍历天然适配“先要孩子结果再做决策”的题目。你只要把最大深度这题做透遍历框架的四种写法等于复习了一遍。5. 实操心得与自测清单5.1 自测用例设计分享一个我平时刷题和交付代码之前都会过的自测流程一把梭下来可以避开九成低级错误。我把测试用例按“形状”分成五类空树null期望0。单节点树TreeNode(1)期望1。满二叉树三层满树期望3。斜树每个节点只有右孩子深度等于节点数期望n。随机形状树左右子树高度不一致手动算好期望值。这五类覆盖了最大深度题目的所有边界情况。特别是“空树”和“斜树”一个测出口一个测递归深度缺一不可。你只需要把这些用例写成单元测试或者直接在main函数里手动构建后打印输出一次跑完。5.2 我个人的代码习惯最后说点我自己的习惯。第一凡是写递归我都会在函数注释里写清楚“递归函数的作用、入参、返回值、终止条件”这个注释帮我省了大量回头排查的时间。第二二叉树的题我优先考虑能不能用递归表达清楚如果涉及大深度、高并发或者需要反复执行的线上代码我直接用迭代方案不给自己挖坑。第三排查运行时错误时我不凭肉眼猜而是先看异常堆栈定位到具体行号再对照上面对应的速查表。还有一个小技巧是我在一道题上踩过坑之后总结出来的递归合并时不要把所有逻辑挤在一行返回里。如果你的主流程很复杂先拆成局部变量比如int leftDepth maxDepth(root.left);int rightDepth maxDepth(root.right);然后再合并返回。这样一旦结果不对你用断点就能看到左右子树的返回值分别是什么排查成本比盯着一行嵌套的1 Math.max(...)低得多。这些习惯看似琐碎但在实际开发和面试中帮了我很多。递归、二叉树、最大深度这三个关键词组合在一起背后其实是“以一种简短的代码处理复杂的层级结构”的思维范式。把这道题吃透你对递归的理解、对栈的把握、对异常边界的敏感度都会明显上一个台阶。下次再有人写错maxDepth或报空指针你甚至不用看代码问一句“你判空了吗”就能定位问题——这就是经验带来的效率。