二叉树最大深度：递归、DFS与BFS的三种解法深度解析-北京尧图网络

刷 LeetCode Hot100 刷到第 28 题的时候说实话我已经有点疲了而这题《104. 二叉树的最大深度》看上去就是那种白给的简单题。但真把它掰开揉碎以后我发现它其实是递归、DFS、BFS、分治思想的一块绝佳试金石里面值得讲的细节比表面上多得多。这篇文章我就围绕这道题把我实际刷题、写代码、调试、扩展的完整过程整理出来。适合正在刷 Hot100 的同学也适合准备面试想在二叉树问题上建立体系的人——你可以把这题当成理解树形结构遍历的基准点后面很多中等难度题都是从这里延伸出去的。1. 从题目定位说起这道送分题为什么值得认真拆1.1 题目到底在问什么题目给一棵二叉树要求返回最大深度。这里的深度定义是从根节点到最远叶子节点路径上的节点数。注意是节点数。一棵只有一个根节点的树最大深度是 1空树直接返回 0。这个定义和边数的定义差 1我见过不少人在这里搞混尤其遇到空树的时候容易在 0 和 1 之间犯迷糊。LeetCode 的示例很明确root [3,9,20,null,null,15,7]输出是 3。因为最长路径是 3-20-15或 3-20-7三个节点深度为 3。那这个最大到底是什么意思一棵树可能有多个叶子节点最远那个叶子所在的路径深度就是我们要的答案。换句话说我们需要比较所有从根到叶子路径的长度取最大值。这个描述本身就暗示了两种常见做法一种是递归分解一种是层序扫描。前者对应 DFS 深度优先搜索后者对应 BFS 广度优先搜索。1.2 它在 Hot100 里的承上启下作用很多人把这道题归为简单题里最水的之一但我更愿意把它看作 Hot100 中二叉树专题的枢纽。为什么这么说因为它的解法几乎可以无缝平移到后面一堆题目上最大深度稍微改一下判断条件就是《110. 平衡二叉树》里的高度比较记录横穿节点的左右深度之和就是《543. 二叉树的直径》把递归返回值从整数换成布尔值就是一类子树是否满足性质的问题。再往后层序变体《102. 二叉树的层序遍历》、《199. 二叉树的右视图》本质上都是在 BFS 遍历时保存额外状态。所以我建议大家别急着把这题划过去而是用一个更高的视角去写今天你在这道题上花的时间未来会在至少五道中等题上还给你。我自己刷了两遍这题第一遍只会递归第二遍把迭代也写透了之后再碰平衡二叉树和直径题时思路基本是秒出。2. 递归解法三行代码背后的分治思想2.1 先写出最简单的版本二叉树的递归解法堪称模板级代码。JavaScript 版var maxDepth function(root) { if (root null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; };Python 版等价实现class Solution: def maxDepth(self, root: Optional[TreeNode]) - int: if root is None: return 0 return 1 max(self.maxDepth(root.left), self.maxDepth(root.right))代码是真的短短到让人怀疑这也能算 LeetCode 题但我想强调看懂这段代码和真正吃透这段代码是两回事。闭着眼睛默写不出问题不代表你理解了为什么这里的返回值要加 1、为什么取最大值。2.2 为什么递归这样写是正确的我们把问题拆一下。对于任意一个节点node以它为根的子树的最大深度等于什么等于以它的左孩子为根的子树最大深度和以它的右孩子为根的子树最大深度中较大的那个再加上 1。加上这 1 是什么意思就是当前节点自身占的一层。你看这个递推式就是depth(node) 1 max(depth(left), depth(right))。边界条件是如果节点为空这棵树不存在深度为 0。这个拆法的本质是分治把原问题划分成两个规模更小的子问题左子树、右子树分别求解再合并结果。递归调用栈在逻辑上走的是一个后序遍历——先深入左子树到底再深入右子树到底最后回到根节点做合并。正是因为这个特性它也被归为 DFS深度优先搜索。我建议读者在心里模拟[3,9,20,null,null,15,7]这棵树的过程根节点 3 问左子树 9 多深9 是叶子它的左右孩子都是 null返回0 1 1根节点 3 再问右子树 2020 的左孩子 15 和右孩子 7 都返回 120 自己返回1 max(1,1) 2根节点最后返回1 max(1,2) 3。逻辑链条非常清晰。2.3 复杂度分析和栈溢出的真实风险时间复杂度是 O(n)因为每个节点都被访问一次。空间复杂度是 O(h)h 是树的高度递归过程中系统栈最深会压到树高那么深。理想平衡树 h log₂n空间 O(logn)最坏情况树退化成一条单链表h n空间 O(n)。经常有人问递归这么深会不会栈溢出这要分环境讨论。浏览器和 Node.js 默认栈深度大约是 1 万层到 1.5 万层之间视具体环境而定。Python 默认递归深度限制约 1000 层但 LeetCode 对多数树用例树高不会超过 1000所以大部分情况下没问题。如果你在极端用例比如一条 10 万层链路上跑递归那确实可能爆栈。这时候就要转用迭代写法这也是为什么下一节的内容在面试里那么重要——面试官一旦问你能不用递归做吗本质就是在考察你对函数调用栈的替代方案熟不熟悉。3. 迭代解法当面试官说不要用递归时怎么办3.1 BFS 层序遍历每遍历完一层深度加一如果不用递归最直观的就是 BFS 层序遍历。我们用队列维护当前层的所有节点每处理完一整层深度就加 1。JavaScript 基础版var maxDepth function(root) { if (root null) return 0; let queue [root]; let depth 0; while (queue.length 0) { let size queue.length; // 当前层的节点数这一步是关键 for (let i 0; i size; i) { let node queue.shift(); if (node.left ! null) queue.push(node.left); if (node.right ! null) queue.push(node.right); } depth; } return depth; };这里我强调几个细节。第一size queue.length必须在进入内层循环前固定住因为我们遍历的是进入 while 时队列里的所有节点也就是当前层内层循环里queue.push会不断往队列尾部加下一层的节点如果我们用动态的queue.length做循环条件就会把下一层也混进当前层深度计数直接错乱。第二queue.shift()在 JavaScript 里是 O(n) 的因为数组头部弹出要移动后面所有元素。数组越大性能越差。在 LeetCode 上跑小规模用例没感觉但在大规模链式树上会有明显性能损耗。更稳的写法是用一个索引指针模拟队列而不是用原生数组的 shiftvar maxDepth function(root) { if (root null) return 0; let queue [root]; let head 0; let depth 0; while (head queue.length) { let size queue.length - head; // 当前层剩余节点数 for (let i 0; i size; i) { let node queue[head]; head; if (node.left ! null) queue.push(node.left); if (node.right ! null) queue.push(node.right); } depth; } return depth; };这样弹出的逻辑就变成了移动队头指针本质是 O(1)只有入队时偶尔扩容。写法和 shift 版本心智负担差不多但性能上一个在天上一个在地下。我个人建议所有 JavaScript 刷题者在写 BFS 时都用指针模拟队列养成习惯。queue.length - head算的是当前层节点数因为 head 之前的节点已经算是出队了。BFS 的复杂度同样好分析时间 O(n)空间 O(w)其中 w 是队列里最多同时存在的节点数。完全二叉树最后一层最多约 n/2 个节点所以空间最坏 O(n)。3.2 用栈模拟 DFS状态压栈比想象中简单既然递归本质是系统调用栈我们当然可以自己开一个栈来模拟递归过程。一个很自然的做法是栈里存两个值——节点本身、以及该节点当前的深度。每弹出一个节点就用它的深度去更新最大值然后把左右孩子带depth 1压进去。var maxDepth function(root) { if (root null) return 0; let stack [[root, 1]]; // 每个元素是 [node, depth] let ans 1; while (stack.length 0) { const [node, depth] stack.pop(); ans Math.max(ans, depth); if (node.left ! null) stack.push([node.left, depth 1]); if (node.right ! null) stack.push([node.right, depth 1]); } return ans; };这个写法我第一次看的时候觉得有点作弊——它没改变遍历的本质只是把递归的状态走到哪一层、当前深度是多少显式地存到栈里。但正是这种显式化让我们摆脱了对系统调用栈的依赖即使树高 10 万也不会爆栈。一个小技巧如果不想用二维数组可以用两个平行栈一个存节点一个存深度。两种方式没有本质区别只是复杂度和可读性的取舍。我写的时候更偏向二维数组因为[node, depth]的配对关系一目了然不容易出现节点和深度没对齐的 bug。3.3 三种解法横向对比我把三种解法放在同一张表里对比方便大家快速抓到核心差异解法遍历方式额外空间代码量核心优势适用场景递归 DFS后序O(h)最少逻辑直接、契合分治思想默认首选、面试手写迭代 BFS层序O(w)中等深度随层数自然递增需要同时处理层信息时迭代 DFS栈模拟O(h)中等偏多无爆栈风险、状态可扩展极端链式树、避免递归时我个人觉得面试中如果面试官没有明确限制先写递归是性价比最高的选择因为它最简洁也最容易解释。如果面试官追问性能问题怎么办能迭代吗你再切换到 BFS 或栈 DFS。但注意切换顺序别搞反——千万不要上来就写迭代除非题目明确要求否则会让面试官觉得你没有掌握递归这个更自然的思维方式。4. 边界条件与常见错误越是简单题越容易栽跟头4.1 最大深度和最小深度是完全不同的题围绕深度问题最容易踩的坑其实是最小深度。同样是 LeetCode有一道《111. 二叉树的最小深度》定义是最短路径上的节点数。注意最小深度不是把 max 换成 min 就完了。为什么看一个例子root [1, null, 2]也就是根节点只有右孩子左孩子为空。如果无脑换 min你会得到左子树深度 0右子树深度 1最终1 min(0,1) 1。但正确答案是 2——因为最小深度要求是到叶子节点而根节点并不是叶子它还有右孩子。空指针不能代表一棵深度为 0的子树参与比较因为空子树上根本没有叶子。解决方法是当某个孩子为 null 时忽略它只看非空孩子那一边或者单独处理左右孩子都为空返回 1当前节点是叶子只有一个孩子非空返回该孩子的递归结果加 1两个孩子都非空才返回较小值的加 1这个坑在最大深度里不存在因为最大深度取 max空子树深度 0 永远不会成为最大值除非整棵树为空。但也正因为如此很多人刷完最大深度后直接去刷最小深度会原地翻车。这个对比值得记下来面试里问深度的题目特别喜欢交替打组合拳。4.2 迭代写法中容易出现的计层错误BFS 迭代里最常见的 bug 就是不固定当前层大小。我第一次写的时候把内层循环写成了for (let i 0; i queue.length; i)结果内层一边出队一边入队queue.length一直变大循环怎么都退不出来最后超时。这个错误非常有代表性因为新手很容易把遍历队列和遍历当前层混淆。记住层序遍历的节奏是进入 while 时队列里装的全是当前层的节点先把当前层节点数记下来也就是size queue.length - head只消费 size 个节点期间新入队的节点属于下一层当前层消费完深度加 1队列里剩下的正好是下一层完整节点还有一个常见问题深度加 1 的位置。有人习惯初始化 depth 1然后进入 while 后再加有人习惯最后加。关键是要和你自己规定的空树返回几保持逻辑一致。我的做法是空树返回 0只要 while 进入过一次说明至少有一层节点被处理depth 就加 1最终返回的 depth 一定是层数。每次写完恨不得用[1,2,3]这种普通三层树先自测一遍。4.3 递归里那些憨憨错误别笑我在实际写递归时真的踩过这些把Math.max(...)写成Math.min(...)。这道题里刚好不会报错但答案在某些用例下完全不对而且因为逻辑没冲突非常难查。空树返回 1。这样一棵空树会被算成深度 1所有答案整体偏移一层。这个问题在自测时最容易发现但如果你只跑 LeetCode 的示例示例里有root []吗没有。示例全是非空树你可能提交后才知道错了。递归参数写错比如maxDepth(root)而不是maxDepth(root.left)——这种属于手滑但在一棵深树上会无限递归直到栈溢出报错还特别不明显。混淆节点数和边数。如果题目按节点数定义空树返回 0、根节点深度 1如果按边数定义空树返回 -1 或 0 的约定会完全不同。我这道题卡过一次因为之前做的某道题用边数定义后面刷到类似题时默认套错了。我给自己定的规矩是每道树相关题目先看示例和评论区确认深度定义永远不直接照搬上一题的结论。4.4 关于 LeetCode 环境的一个隐藏细节用 JavaScript 在 LeetCode 上跑题时很多人忽略了一个点LeetCode 的 JavaScript 运行环境是 Node.js 而不是浏览器默认栈大小限制会比浏览器严格。虽然刷题时几乎碰不到递归溢出但在自己电脑上跑极端用例时如果直接用node script.js可能会发现同样的递归代码本地报错线上却通过了。遇到这种情况不要怀疑代码逻辑先查一下是不是本地 Node 栈太小可以试着把递归改成迭代验证一下。我在本地构造一棵一万层的链式树测过递归版在 Node 里确实会崩迭代版则安然无恙。这个测试也让我真正理解了尾递归优化不可靠、显式栈更稳这句话。5. 变体与延伸一道最大深度能带出多少题5.1 直接变体平衡二叉树、直径、最小深度最大深度是二叉树问题的万恶之源我们从这里可以延伸到至少三道经典题《110. 平衡二叉树》判断任意节点的左右子树高度差是否不超过 1。你可以先写一个求深度的辅助函数再对每个节点判断。但这样会重复遍历时间复杂度 O(n²)。更优解法是后序遍历时同时返回当前子树高度和是否平衡一旦发现不平衡立即剪枝时间复杂度降到 O(n)。是不是很眼熟height 1 max(leftHeight, rightHeight)和最大深度一模一样只是多了个布尔值判断。《543. 二叉树的直径》直径是任意两个节点间路径长度边数的最大值。对每个节点来说经过它的最长路径长度就是leftHeight rightHeight左右深度之和注意这里是边数口径。遍历过程中用一个全局变量不断更新最大值。这道题如果不先理解最大深度的递推式很难想通为什么要在递归里同时更新全局变量。《111. 二叉树的最小深度》前面已经说了一个坑。如果最大深度是取 max、空子树天然是 0最小深度就是要小心空子树不能当作 0 参与比较。这两题一起刷你会发现同一套递归模板在边界条件下会露出完全不同的幺蛾子。5.2 从层序变体右视图、每层最大值、锯齿遍历BFS 解法对最大深度题来说只是个替代方案但对下面这些题来说是正主《199. 二叉树的右视图》在层序遍历时只把当前层最后一个节点的值加入结果数组。求每层最大值/平均值同样在层序遍历时对每一层做聚合。《103. 二叉树的锯齿形层序遍历》层序号奇偶交替决定入结果数组的顺序。这些题难就难在对层这个概念的处理。而二叉树的层是什么怎么计算当前层节点数这个基本功正是你在最大深度题的 BFS 解法里学到的。所以我一直说简单题不是用来刷过去的是用来积累解题工具的。5.3 我实际刷 Hot100 时的节奏和笔记方式刷完这题的时候我已经到了第 28/100 的位置。说实话这个阶段很容易陷入一天刷十道简单题的虚假充实感里。我自己调整了几次策略最后沉淀下来的方法有三个第一每道题至少写两种解法。像最大深度这种题递归 3 行写完再花 10 分钟写 BFS 和栈 DFS等价于一道题吃透三种遍历思想。后面遇到 BFS 变体时你会感谢自己当初多写的这 10 分钟。第二用对比表格整理相似题。我单独建了一个二叉树深度的知识卡片把最大深度、最小深度、平衡二叉树、直径四道题放在一起列清楚定义的差别节点数还是边数、要不要绕过空子树、返回值是高度还是布尔值。做题最怕的就是每道题都会合在一起变个说法就懵而这种卡就是对抗变说法的武器。第三定期重刷。我给自己定的复习窗口是第 7 天、第 21 天、第 45 天。像最大深度这种题第一次刷只是入门第二次刷时试着不看代码直接写三种解法第三次刷时可以顺带把四个变体一次性过一遍。每一次重刷的视角都不同这也是刷题记忆最牢固的方式。6. 一些刷题之外的题外话这道题从代码量上看是 Hot100 里最轻量的一档但它对我的意义不亚于任何一道 Hard。原因很简单它把树的递归这个所有树形结构题的基础模型压缩到了 3 行代码里。你把它吃透了后面不管遇到的是序列化二叉树、最近公共祖先、还是一大片 DP 型树题至少不会在最基础的高度计算上卡壳。最后分享一个小技巧如果你想验证自己对这题的掌握程度试着在纸上不写代码、只用箭头和数字模拟一遍递归调用栈再把递归改成迭代重写一遍。如果能顺利完成那这道题才算真正归你了。往后刷 Hot100 的中等难题时你会不止一次想起今天这个看似简单的 3 行递归。

二叉树最大深度：递归、DFS与BFS的三种解法深度解析

相关推荐

终端里的AI打砖块：用Bash实现Claude流式响应可视化

价格、服务、合规、退款、交付补天云计算机视觉应用实践软件产品（A系列）有哪些销售政策？软件产品价格是多少？技术服务按什么收费标准？面向大中专院校｜纯软件CPU离线部署｜14大模块/70项实践案例

AI智能体循环工程-第6章第3节-环境搭建与第一个循环-50行跑通最小ReAct循环

更多资讯

roLabelImg源码解析：旋转框标注工具从安装到二次开发

数据库图书管理系统实训全流程：从E-R图到JDBC事务与并发控制

图像质量评估模型Python实战：PSNR/SSIM/BRISQUE量化指南

CLion搭建树莓派Pico C/C++开发环境：从零到断点调试全攻略

ESP32 上实现 ONVIF 相机：从组件搭建到 NVR 添加实战

UC网盘下载不限速办法：亲测有效的免费提速思路与操作指南

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？