1. 先把这道题吃透它为什么能进hot100hot100里有一类题是真正的“基础分水岭”104.二叉树的最大深度就是其中之一。这道题让很多刚开始刷二叉树的人第一次接触到递归三板斧也让不少刷题有段时间的同学第一次被“运行时错误”整得怀疑人生。最大深度本身不难但如果你只记住了一个递归模板却没有想清楚“深度是怎么一层层传上来的”后面做平衡二叉树、直径、路径和这类题都会卡壳。这篇文章不只想讲AC代码更想聊聊为什么写二叉树程序时总是报运行时错误以及怎么把“深度”这个概念迁移到hot100一系列相关题上。先说这道题本身的定位。LeetCode 104题“二叉树的最大深度”本质上问的是从根节点出发沿着一条路径一直往下走最多能走多少层。根节点算一层空树算0层。很多教程把它归类为“二叉树遍历”的入门题但我更愿意把它当成“递归状态设计”的启蒙题——因为它的解法和后序遍历天然绑定而一旦你接受了这个绑定后面一大半二叉树题目的思路都会自动打开。这道题适合谁来刷我的建议是刚学完数组、链表、哈希表准备进入树形结构的人以及已经写过不少题但遇到二叉树就只会背模板、说不清原理的人。前者能通过它建立递归的直觉后者能通过它补上“回溯过程”这一课。总之它绝不只是“一道简单题”而是hot100里二叉树模块的一个枢纽节点。2. 解法背后的核心思路递归、后序、深度传递2.1 递归三要素先想清楚“子问题”是什么很多人写递归时有个习惯拿到题就开始写函数体写到一半发现边界条件没想清楚再回头改。这个习惯在简单的题上问题不大但深度一旦超过两层就会漏掉分支。我建议所有二叉树递归题都先回答三个问题这个函数要返回什么、当前节点要做哪些事、空节点怎么处理。对应到最大深度这道题函数定义maxDepth(node)表示以node为根的子树的最大深度。当前节点要做的事比较左子树和右子树的深度取较大者再加1。空节点处理如果node是null深度为0。一旦这三个问题想清楚了代码几乎是直接翻译不需要“感觉”。那为什么一定要先算左右子树再算当前节点因为一个节点能提供的深度信息只有一个它本身的1层加上下面最长那条路径的层数。你没有左右子树的结果就拼不出这个答案。这种“先孩子、后自己”的处理顺序正是后序遍历的逻辑。2.2 从归并思维理解深度把答案从叶子一层层抬上来后序遍历最直观的理解可以想象成公司里层层上报数据。叶子节点手上没有下属所以它们上报“我这里深度是1”。中间节点接到左右两个下属上报的数字后取一个较大的再加上自己这层继续往上汇报。根节点最后拿到整个树的深度。整个过程不是“从根一路往下数”而是“从叶子一路往回算”这是初学二叉树时最容易拧巴的地方。我用一个生活化的场景解释你站在一棵树的根部想知道树有多高。你不会真的从根爬到树顶边爬边数。更靠谱的做法是问左、右两个主要枝桠各自多高取高的那个再加上从地面到分叉点这段高度。递归做的事就是这个——“高度”是由子枝桠决定的不是由根自己决定的。很多同学在纸上画递归过程时会画出一棵向下开的“调用树”但真正的返回过程是反着往上走的理解了这一点递归代码就不会写得莫名奇妙。2.3 递推公式的推导为什么是1 max(leftDepth, rightDepth)如果一定要给这道题总结一个公式那就是maxDepth(node) 0, 当 node null maxDepth(node) 1 max(maxDepth(node.left), maxDepth(node.right)), 当 node ! null这个公式里最容易被忽略的是那个“1”。它代表当前节点自身这一层。很多人背代码时会把Math.max(leftDepth, rightDepth) 1里的1漏掉一提交发现结果总是比答案小1这就是没想清楚“当前节点自身也算一层”这个含义。另一个常见问题是把空节点深度错算为-1或者1这会让所有结果整体偏移而这在LeetCode的测试用例里往往直接判错。那为什么空节点必须是0而不是-1因为深度计算的基点是“没有节点就没有层数”。如果你把null的深度设成-1那么1 max(-1 1, -1 1)会导致叶子节点深度变成0根节点深度变成0整体少一层。反过来设成1会让空子树也被当成一层答案偏大。所以空节点返回0是这个公式能自洽的地基。2.4 复杂度其实也值得说两句时间复杂度是O(n)因为每个节点都会被访问一次空间复杂度是O(h)h是树的高度。递归调用栈的深度就是树高最坏情况下树退化成一条链空间复杂度为O(n)。这个看似“顺便一提”的结论其实是后面应对“运行时错误”的关键——很多栈溢出问题就是栽在“树高等于节点数”这个特殊情况上。3. 写二叉树程序时为什么总是报运行时错误一次完整的排查实录3.1 先分清错误类型StackOverflow、NullPointer、还是结果不对在讨论具体错误前我想先强调一个容易被忽略的事实很多同学把“答案不对”也统称为报错但运行时错误Runtime Error和答案错误Wrong Answer在LeetCode上是两种完全不同的反馈。运行时错误意味着程序在执行过程中崩了常见的是StackOverflowError、NullPointerException答案错误则是程序跑完了只是结果不对。排查思路完全不同前者先找“哪一行崩了”后者先找“逻辑哪里偏了”。以104题为例如果你写了这样的代码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为null时第一行就会访问root.left直接抛NullPointerException。LeetCode的测试用例里几乎必然包含空树所以这种代码提交必挂。这时候先别急着改逻辑你的问题是缺少“空节点保护”。3.2 最隐蔽的坑栈溢出与递归深度失控另一种极常见的运行时错误是StackOverflowError。如果你输入的不是一颗稍微倾斜的普通树而是一棵退化成链的树每个节点只有左孩子或只有右孩子递归深度就会等于节点数量。假设一棵二叉树有10万个节点且全部偏向一侧递归函数调用10万层时Java默认的虚拟机栈很可能会溢出。遇到这种问题很多人的第一反应是“是不是我递归写错了”其实你的逻辑完全正确只是“递归深度太深超出栈的容量”。这种时候有两个方向一是把递归改成迭代二是在面试场景中跟面试官说明“递归解法在退化成链时可能会栈溢出所以实际工程中我更倾向用BFS”。如果你能主动说出这句话比背十道代码都加分。我记得有一次在本地IDE里测一个深度很大的用例直接报StackOverflowError破案方式是把异常栈打出来发现溢出发生在maxDepth方法的递归调用处。那一刻才真正理解了“空间复杂度O(h)”不是一句空话——h是什么h就是递归调用栈的深度而栈的深度是有物理上限的。3.3 本地能过、提交就挂全局变量没清空的典型翻车还有一种“运行时错误”非常阴险代码逻辑没问题但你在类里定义了一个成员变量用来记录答案比如class Solution { int ans 0; public int maxDepth(TreeNode root) { dfs(root, 1); return ans; } }如果ans没有在每次调用maxDepth前重置第一次跑一个深度为5的树后ans变5第二次跑一个深度为3的树ans可能仍然是5因为dfs内部只在比当前ans大的时候更新它。在LeetCode的评测环境下每次测试会创建新的Solution实例所以这个问题不算特别致命但如果你在本地用同一个对象连续跑多个测试用例就会得到非常诡异的结果。解决方式很简单能用局部变量就不要用全局变量非要全局变量就在入口函数里先重置。这个习惯在写其他更复杂的二叉树题比如直径、路径和时尤为重要因为那些题更依赖“在递归过程中更新外部变量”。3.4 一套通用的二叉树BUG排查方法论结合踩过的坑我总结了一套排查“二叉树报错”的固定流程先看异常类型如果是NullPointerException八成是某个节点为null时还访问了它的子节点检查递归入口和终止条件。如果是StackOverflowError优先怀疑递归深度过深尝试用迭代或增加递归基。如果是答案错误找一个最小用例比如只有根节点的树、左单链树在纸上画出递归过程手算一遍期望值。善用打印在递归函数开头打印当前节点值、当前深度能快速看出递归是否走到了预期分支。用极端用例测试空树、只有根节点、左右子树深度差巨大的树、彻底倾斜的链状树。这五个用例覆盖了二叉树八成以上的边界bug。4. 迭代方案与递归的取舍别只会背递归模板4.1 BFS层序遍历数一层、加一层最直观的深度计数既然递归在某些场景下会栈溢出迭代解法至少要知道一种。最简单的是层序遍历用队列实现。它的思路很直白把根节点入队然后一层一层往外弹每处理完一整层的节点深度就加1。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()。由于队列在循环过程中会不断加入新节点如果直接在while里动态判空你就不知道当前层到底有多少节点。先锁住size再一次性处理完这一层才能保证每轮循环恰好对应一层。我见过很多同学卡在这一步把queue.size()放进for循环里每次重新获取结果边界错乱深度永远多一层。4.2 DFS迭代用双栈模拟递归过程如果你想保留“深度优先”的访问顺序也可以用两个栈一个存节点一个存当前深度。每弹出一个节点就尝试把它的左右孩子压入同时把深度加1。public int maxDepth(TreeNode root) { if (root null) return 0; DequeTreeNode stack new ArrayDeque(); DequeInteger depthStack new ArrayDeque(); stack.push(root); depthStack.push(1); int max 0; while (!stack.isEmpty()) { TreeNode node stack.pop(); int depth depthStack.pop(); max Math.max(max, depth); if (node.left ! null) { stack.push(node.left); depthStack.push(depth 1); } if (node.right ! null) { stack.push(node.right); depthStack.push(depth 1); } } return max; }双栈的结构实际上是把“函数调用栈”手动搬到了堆上所以不受虚拟机栈大小的限制。有人可能会问为什么要用双栈而不是把(node, depth)拼成一个对象压入因为双栈在某些语言里性能更优也方便理解“同步弹出”的配对关系。如果你更习惯封装一个Pair也没有任何问题核心逻辑是等价的。4.3 核心区别对比什么时候用递归什么时候用迭代维度递归迭代BFS迭代DFS代码可读性极高和递推公式一致高需要理解层计数技巧中等需要维护深度栈空间复杂度O(h)受系统栈限制O(w)w是最大层宽度O(h)但使用堆空间退化链状树风险容易栈溢出安全安全面试观感最符合直觉体现对树结构的理解体现代码掌控力训练建议是先用递归把逻辑练到滚瓜烂熟再熟悉一种迭代解法。面试时如果只允许写一种递归通常最快但如果面试官追问“最坏情况下空间会不会有问题”你能立刻切到BFS版本就是明显的加分项。5. 从一道题拓展到一类题深度问题的变体与迁移5.1 最小深度为什么不能直接套max的模板hot100和力扣题库里紧接着最大深度最常见的就是最小深度。很多同学把最大深度代码里的Math.max换成Math.min就交了结果翻车。原因在于当某个节点的左子树为空时它的最小深度不等于0而应该去看右子树的最小深度。因为“从根到最近叶子节点”的路径中空子树并不是一条有效路径。正确的思路是分情况讨论public int minDepth(TreeNode root) { if (root null) return 0; if (root.left null) return minDepth(root.right) 1; if (root.right null) return minDepth(root.left) 1; return Math.min(minDepth(root.left), minDepth(root.right)) 1; }这个题特别适合拿来检验自己是否真的理解了“深度”的定义而不只是背了一个求最大值的模板。我在实际给朋友讲题时发现很多人会想当然地认为空子树深度是0所以最小值也该是0。这里的坑在于空子树并不包含叶子节点而最小深度要求的是“包含叶子节点”的最短路径。5.2 平衡二叉树深度判断后序返回结构另一个高频变体是判断平衡二叉树110题它要求每个节点左右子树高度差不能超过1。这题的解法就是在后序遍历中同时返回“当前子树高度”和“是否平衡”。如果你只从最大深度里学会了Math.max(left, right) 1那再学这题会非常顺一个节点算完深度后顺手检查左右高度的差值。这类“返回结构升级”的思路很关键。最大深度只需要返回int但很多树形DP问题都需要返回一个更复杂的结构比如(深度, 是否平衡)或者(深度, 直径)。先把104题的单值返回练熟后面才能驾驭多值返回这是二叉树递归进阶的必经之路。5.3 N叉树最大深度与直径题同一套思路的不同外衣N叉树的最大深度559题几乎是把二叉树版本平移到多叉树遍历所有孩子取最大深度再1。如果你用的是ListNode children只需要加一个for循环逻辑完全不变。这让我意识到“最大深度”这个考点本质是“树的深度的定义和递归计算”并不限定二叉树。再往后走二叉树的直径543题就更有意思了。直径可以理解为“经过某个节点的左右子树深度之和的最大值”。求解时同样是在后序遍历中拿到左右子树的深度但更新答案用的是leftDepth rightDepth而返回给父节点的是Math.max(leftDepth, rightDepth) 1。这个小小的“返回值与答案不同”的设计很多人一开始会想不明白。但只要你想通了“当前节点既要向父节点汇报自己的高度又要顺便计算经过自己的直径”整道题就豁然开朗了。5.4 从深度到路径hot100二叉树题的串联学习方法如果你正在刷hot100我建议把二叉树相关题按这个顺序串在一起先做104最大深度再做226翻转二叉树然后做101对称二叉树接着做112路径总和再做102层序遍历。你会发现它们都共享同一个“遍历框架”只是在不同时机处理不同的业务逻辑。深度相关的题练完后可以尝试把“最大路径和”124题当成一个进阶目标。这道题经常被人在分类里标成动态规划但它其实更像“后序遍历状态归并”。你从104题里学到的“返回子树深度”在124题里变成“返回子树能提供的最大贡献路径和”整个思维迁移非常自然。这也是为什么我一直强调104题不只是让你AC而是让你建立一套“树形结构问题”的思考框架。6. 我的刷题节奏与个人心得6.1 一道题值得反复刷三次在hot100里104是一个可以反复利用的题目。我的建议是分三遍第一遍只看题解用递归AC目标是理解后序遍历第二遍隔几天后在不看代码的情况下手写出BFS版本第三遍再间隔一周把这道题讲给一个完全不懂递归的人听要求对方能理解“深度从叶子往上算”。第三遍听起来有点玄学但确实高效。讲题的过程会逼你把模糊的认知变成清晰的表达尤其是“为什么必须取左右子树结果后再计算当前节点”这件事讲得清楚说明真懂了。如果只是背代码很容易在第三遍被问住。6.2 一个让我印象深刻的翻车现场有一次我在本地做测试Solution类里有一个全局变量ans连续跑了三个测试用例前两个结果都正确第三个深度更小但输出的还是上一个用例的答案。我当时第一反应是代码逻辑问题后来一查发现全局变量没有重置。从那次以后我在任何递归题里都养成了“先重置全局状态”的习惯也尽量避免使用成员变量能用局部变量就绝不外提。还有一次是帮别人排查代码对方报“运行时错误”我看了一眼他在递归函数里写了两个终止条件其中一个return了ans另一个没有返回值编译器直接报错。这种情况在LeetCode上有时会表现为missing return statement本地IDE会直接标红但只要换成有些平台编译信息不友好就会让人误以为是自己逻辑错了。所以写递归时确保每个if分支都有明确的return是我反复强调的底线。6.3 最后分享一个小技巧刷二叉树题时强烈建议养成“先画图、再写码”的习惯。哪怕脑筋里画一遍也行标出根节点、左右子树、递归边界。只盯着代码看是看不出问题的但一比对着图写递归条件空指针和边界漏判基本能规避大半。104这道题看上去简单却是养成这个习惯成本最低的一道题。等你把画图变成肌肉记忆再遇到hard难度的树形题时就不会慌到无从下手。
二叉树最大深度：从递归到迭代，详解后序遍历与运行时错误
1. 先把这道题吃透它为什么能进hot100hot100里有一类题是真正的“基础分水岭”104.二叉树的最大深度就是其中之一。这道题让很多刚开始刷二叉树的人第一次接触到递归三板斧也让不少刷题有段时间的同学第一次被“运行时错误”整得怀疑人生。最大深度本身不难但如果你只记住了一个递归模板却没有想清楚“深度是怎么一层层传上来的”后面做平衡二叉树、直径、路径和这类题都会卡壳。这篇文章不只想讲AC代码更想聊聊为什么写二叉树程序时总是报运行时错误以及怎么把“深度”这个概念迁移到hot100一系列相关题上。先说这道题本身的定位。LeetCode 104题“二叉树的最大深度”本质上问的是从根节点出发沿着一条路径一直往下走最多能走多少层。根节点算一层空树算0层。很多教程把它归类为“二叉树遍历”的入门题但我更愿意把它当成“递归状态设计”的启蒙题——因为它的解法和后序遍历天然绑定而一旦你接受了这个绑定后面一大半二叉树题目的思路都会自动打开。这道题适合谁来刷我的建议是刚学完数组、链表、哈希表准备进入树形结构的人以及已经写过不少题但遇到二叉树就只会背模板、说不清原理的人。前者能通过它建立递归的直觉后者能通过它补上“回溯过程”这一课。总之它绝不只是“一道简单题”而是hot100里二叉树模块的一个枢纽节点。2. 解法背后的核心思路递归、后序、深度传递2.1 递归三要素先想清楚“子问题”是什么很多人写递归时有个习惯拿到题就开始写函数体写到一半发现边界条件没想清楚再回头改。这个习惯在简单的题上问题不大但深度一旦超过两层就会漏掉分支。我建议所有二叉树递归题都先回答三个问题这个函数要返回什么、当前节点要做哪些事、空节点怎么处理。对应到最大深度这道题函数定义maxDepth(node)表示以node为根的子树的最大深度。当前节点要做的事比较左子树和右子树的深度取较大者再加1。空节点处理如果node是null深度为0。一旦这三个问题想清楚了代码几乎是直接翻译不需要“感觉”。那为什么一定要先算左右子树再算当前节点因为一个节点能提供的深度信息只有一个它本身的1层加上下面最长那条路径的层数。你没有左右子树的结果就拼不出这个答案。这种“先孩子、后自己”的处理顺序正是后序遍历的逻辑。2.2 从归并思维理解深度把答案从叶子一层层抬上来后序遍历最直观的理解可以想象成公司里层层上报数据。叶子节点手上没有下属所以它们上报“我这里深度是1”。中间节点接到左右两个下属上报的数字后取一个较大的再加上自己这层继续往上汇报。根节点最后拿到整个树的深度。整个过程不是“从根一路往下数”而是“从叶子一路往回算”这是初学二叉树时最容易拧巴的地方。我用一个生活化的场景解释你站在一棵树的根部想知道树有多高。你不会真的从根爬到树顶边爬边数。更靠谱的做法是问左、右两个主要枝桠各自多高取高的那个再加上从地面到分叉点这段高度。递归做的事就是这个——“高度”是由子枝桠决定的不是由根自己决定的。很多同学在纸上画递归过程时会画出一棵向下开的“调用树”但真正的返回过程是反着往上走的理解了这一点递归代码就不会写得莫名奇妙。2.3 递推公式的推导为什么是1 max(leftDepth, rightDepth)如果一定要给这道题总结一个公式那就是maxDepth(node) 0, 当 node null maxDepth(node) 1 max(maxDepth(node.left), maxDepth(node.right)), 当 node ! null这个公式里最容易被忽略的是那个“1”。它代表当前节点自身这一层。很多人背代码时会把Math.max(leftDepth, rightDepth) 1里的1漏掉一提交发现结果总是比答案小1这就是没想清楚“当前节点自身也算一层”这个含义。另一个常见问题是把空节点深度错算为-1或者1这会让所有结果整体偏移而这在LeetCode的测试用例里往往直接判错。那为什么空节点必须是0而不是-1因为深度计算的基点是“没有节点就没有层数”。如果你把null的深度设成-1那么1 max(-1 1, -1 1)会导致叶子节点深度变成0根节点深度变成0整体少一层。反过来设成1会让空子树也被当成一层答案偏大。所以空节点返回0是这个公式能自洽的地基。2.4 复杂度其实也值得说两句时间复杂度是O(n)因为每个节点都会被访问一次空间复杂度是O(h)h是树的高度。递归调用栈的深度就是树高最坏情况下树退化成一条链空间复杂度为O(n)。这个看似“顺便一提”的结论其实是后面应对“运行时错误”的关键——很多栈溢出问题就是栽在“树高等于节点数”这个特殊情况上。3. 写二叉树程序时为什么总是报运行时错误一次完整的排查实录3.1 先分清错误类型StackOverflow、NullPointer、还是结果不对在讨论具体错误前我想先强调一个容易被忽略的事实很多同学把“答案不对”也统称为报错但运行时错误Runtime Error和答案错误Wrong Answer在LeetCode上是两种完全不同的反馈。运行时错误意味着程序在执行过程中崩了常见的是StackOverflowError、NullPointerException答案错误则是程序跑完了只是结果不对。排查思路完全不同前者先找“哪一行崩了”后者先找“逻辑哪里偏了”。以104题为例如果你写了这样的代码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为null时第一行就会访问root.left直接抛NullPointerException。LeetCode的测试用例里几乎必然包含空树所以这种代码提交必挂。这时候先别急着改逻辑你的问题是缺少“空节点保护”。3.2 最隐蔽的坑栈溢出与递归深度失控另一种极常见的运行时错误是StackOverflowError。如果你输入的不是一颗稍微倾斜的普通树而是一棵退化成链的树每个节点只有左孩子或只有右孩子递归深度就会等于节点数量。假设一棵二叉树有10万个节点且全部偏向一侧递归函数调用10万层时Java默认的虚拟机栈很可能会溢出。遇到这种问题很多人的第一反应是“是不是我递归写错了”其实你的逻辑完全正确只是“递归深度太深超出栈的容量”。这种时候有两个方向一是把递归改成迭代二是在面试场景中跟面试官说明“递归解法在退化成链时可能会栈溢出所以实际工程中我更倾向用BFS”。如果你能主动说出这句话比背十道代码都加分。我记得有一次在本地IDE里测一个深度很大的用例直接报StackOverflowError破案方式是把异常栈打出来发现溢出发生在maxDepth方法的递归调用处。那一刻才真正理解了“空间复杂度O(h)”不是一句空话——h是什么h就是递归调用栈的深度而栈的深度是有物理上限的。3.3 本地能过、提交就挂全局变量没清空的典型翻车还有一种“运行时错误”非常阴险代码逻辑没问题但你在类里定义了一个成员变量用来记录答案比如class Solution { int ans 0; public int maxDepth(TreeNode root) { dfs(root, 1); return ans; } }如果ans没有在每次调用maxDepth前重置第一次跑一个深度为5的树后ans变5第二次跑一个深度为3的树ans可能仍然是5因为dfs内部只在比当前ans大的时候更新它。在LeetCode的评测环境下每次测试会创建新的Solution实例所以这个问题不算特别致命但如果你在本地用同一个对象连续跑多个测试用例就会得到非常诡异的结果。解决方式很简单能用局部变量就不要用全局变量非要全局变量就在入口函数里先重置。这个习惯在写其他更复杂的二叉树题比如直径、路径和时尤为重要因为那些题更依赖“在递归过程中更新外部变量”。3.4 一套通用的二叉树BUG排查方法论结合踩过的坑我总结了一套排查“二叉树报错”的固定流程先看异常类型如果是NullPointerException八成是某个节点为null时还访问了它的子节点检查递归入口和终止条件。如果是StackOverflowError优先怀疑递归深度过深尝试用迭代或增加递归基。如果是答案错误找一个最小用例比如只有根节点的树、左单链树在纸上画出递归过程手算一遍期望值。善用打印在递归函数开头打印当前节点值、当前深度能快速看出递归是否走到了预期分支。用极端用例测试空树、只有根节点、左右子树深度差巨大的树、彻底倾斜的链状树。这五个用例覆盖了二叉树八成以上的边界bug。4. 迭代方案与递归的取舍别只会背递归模板4.1 BFS层序遍历数一层、加一层最直观的深度计数既然递归在某些场景下会栈溢出迭代解法至少要知道一种。最简单的是层序遍历用队列实现。它的思路很直白把根节点入队然后一层一层往外弹每处理完一整层的节点深度就加1。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()。由于队列在循环过程中会不断加入新节点如果直接在while里动态判空你就不知道当前层到底有多少节点。先锁住size再一次性处理完这一层才能保证每轮循环恰好对应一层。我见过很多同学卡在这一步把queue.size()放进for循环里每次重新获取结果边界错乱深度永远多一层。4.2 DFS迭代用双栈模拟递归过程如果你想保留“深度优先”的访问顺序也可以用两个栈一个存节点一个存当前深度。每弹出一个节点就尝试把它的左右孩子压入同时把深度加1。public int maxDepth(TreeNode root) { if (root null) return 0; DequeTreeNode stack new ArrayDeque(); DequeInteger depthStack new ArrayDeque(); stack.push(root); depthStack.push(1); int max 0; while (!stack.isEmpty()) { TreeNode node stack.pop(); int depth depthStack.pop(); max Math.max(max, depth); if (node.left ! null) { stack.push(node.left); depthStack.push(depth 1); } if (node.right ! null) { stack.push(node.right); depthStack.push(depth 1); } } return max; }双栈的结构实际上是把“函数调用栈”手动搬到了堆上所以不受虚拟机栈大小的限制。有人可能会问为什么要用双栈而不是把(node, depth)拼成一个对象压入因为双栈在某些语言里性能更优也方便理解“同步弹出”的配对关系。如果你更习惯封装一个Pair也没有任何问题核心逻辑是等价的。4.3 核心区别对比什么时候用递归什么时候用迭代维度递归迭代BFS迭代DFS代码可读性极高和递推公式一致高需要理解层计数技巧中等需要维护深度栈空间复杂度O(h)受系统栈限制O(w)w是最大层宽度O(h)但使用堆空间退化链状树风险容易栈溢出安全安全面试观感最符合直觉体现对树结构的理解体现代码掌控力训练建议是先用递归把逻辑练到滚瓜烂熟再熟悉一种迭代解法。面试时如果只允许写一种递归通常最快但如果面试官追问“最坏情况下空间会不会有问题”你能立刻切到BFS版本就是明显的加分项。5. 从一道题拓展到一类题深度问题的变体与迁移5.1 最小深度为什么不能直接套max的模板hot100和力扣题库里紧接着最大深度最常见的就是最小深度。很多同学把最大深度代码里的Math.max换成Math.min就交了结果翻车。原因在于当某个节点的左子树为空时它的最小深度不等于0而应该去看右子树的最小深度。因为“从根到最近叶子节点”的路径中空子树并不是一条有效路径。正确的思路是分情况讨论public int minDepth(TreeNode root) { if (root null) return 0; if (root.left null) return minDepth(root.right) 1; if (root.right null) return minDepth(root.left) 1; return Math.min(minDepth(root.left), minDepth(root.right)) 1; }这个题特别适合拿来检验自己是否真的理解了“深度”的定义而不只是背了一个求最大值的模板。我在实际给朋友讲题时发现很多人会想当然地认为空子树深度是0所以最小值也该是0。这里的坑在于空子树并不包含叶子节点而最小深度要求的是“包含叶子节点”的最短路径。5.2 平衡二叉树深度判断后序返回结构另一个高频变体是判断平衡二叉树110题它要求每个节点左右子树高度差不能超过1。这题的解法就是在后序遍历中同时返回“当前子树高度”和“是否平衡”。如果你只从最大深度里学会了Math.max(left, right) 1那再学这题会非常顺一个节点算完深度后顺手检查左右高度的差值。这类“返回结构升级”的思路很关键。最大深度只需要返回int但很多树形DP问题都需要返回一个更复杂的结构比如(深度, 是否平衡)或者(深度, 直径)。先把104题的单值返回练熟后面才能驾驭多值返回这是二叉树递归进阶的必经之路。5.3 N叉树最大深度与直径题同一套思路的不同外衣N叉树的最大深度559题几乎是把二叉树版本平移到多叉树遍历所有孩子取最大深度再1。如果你用的是ListNode children只需要加一个for循环逻辑完全不变。这让我意识到“最大深度”这个考点本质是“树的深度的定义和递归计算”并不限定二叉树。再往后走二叉树的直径543题就更有意思了。直径可以理解为“经过某个节点的左右子树深度之和的最大值”。求解时同样是在后序遍历中拿到左右子树的深度但更新答案用的是leftDepth rightDepth而返回给父节点的是Math.max(leftDepth, rightDepth) 1。这个小小的“返回值与答案不同”的设计很多人一开始会想不明白。但只要你想通了“当前节点既要向父节点汇报自己的高度又要顺便计算经过自己的直径”整道题就豁然开朗了。5.4 从深度到路径hot100二叉树题的串联学习方法如果你正在刷hot100我建议把二叉树相关题按这个顺序串在一起先做104最大深度再做226翻转二叉树然后做101对称二叉树接着做112路径总和再做102层序遍历。你会发现它们都共享同一个“遍历框架”只是在不同时机处理不同的业务逻辑。深度相关的题练完后可以尝试把“最大路径和”124题当成一个进阶目标。这道题经常被人在分类里标成动态规划但它其实更像“后序遍历状态归并”。你从104题里学到的“返回子树深度”在124题里变成“返回子树能提供的最大贡献路径和”整个思维迁移非常自然。这也是为什么我一直强调104题不只是让你AC而是让你建立一套“树形结构问题”的思考框架。6. 我的刷题节奏与个人心得6.1 一道题值得反复刷三次在hot100里104是一个可以反复利用的题目。我的建议是分三遍第一遍只看题解用递归AC目标是理解后序遍历第二遍隔几天后在不看代码的情况下手写出BFS版本第三遍再间隔一周把这道题讲给一个完全不懂递归的人听要求对方能理解“深度从叶子往上算”。第三遍听起来有点玄学但确实高效。讲题的过程会逼你把模糊的认知变成清晰的表达尤其是“为什么必须取左右子树结果后再计算当前节点”这件事讲得清楚说明真懂了。如果只是背代码很容易在第三遍被问住。6.2 一个让我印象深刻的翻车现场有一次我在本地做测试Solution类里有一个全局变量ans连续跑了三个测试用例前两个结果都正确第三个深度更小但输出的还是上一个用例的答案。我当时第一反应是代码逻辑问题后来一查发现全局变量没有重置。从那次以后我在任何递归题里都养成了“先重置全局状态”的习惯也尽量避免使用成员变量能用局部变量就绝不外提。还有一次是帮别人排查代码对方报“运行时错误”我看了一眼他在递归函数里写了两个终止条件其中一个return了ans另一个没有返回值编译器直接报错。这种情况在LeetCode上有时会表现为missing return statement本地IDE会直接标红但只要换成有些平台编译信息不友好就会让人误以为是自己逻辑错了。所以写递归时确保每个if分支都有明确的return是我反复强调的底线。6.3 最后分享一个小技巧刷二叉树题时强烈建议养成“先画图、再写码”的习惯。哪怕脑筋里画一遍也行标出根节点、左右子树、递归边界。只盯着代码看是看不出问题的但一比对着图写递归条件空指针和边界漏判基本能规避大半。104这道题看上去简单却是养成这个习惯成本最低的一道题。等你把画图变成肌肉记忆再遇到hard难度的树形题时就不会慌到无从下手。
