1. 先说清楚二叉树的“深度”到底是什么很多人拿到“计算二叉树的深度”这个题第一反应是“不就递归一下吗”。确实递归解法五行内搞定但如果你只在背代码遇到“为什么空树返回0”、“为什么最大深度不是左右子树深度之和”、“递归栈溢出了怎么办”这些追问时大概率会卡壳。我在实际面试和写业务代码时被这几个问题折磨过不止一次所以先把定义和心智模型聊透。二叉树的深度严格定义是从根节点到最远叶子节点的最长路径上的节点总数。注意是“节点总数”所以只有一个根节点的树深度是1而不是0。空树呢树里一个节点都没有深度自然是0。这个边界很多人一开始会混淆。另外一个容易混淆的概念是“高度”高度通常指某个节点到最远叶子节点的最长路径上的边数或节点数看具体语境而深度经常和“层数”混用。在我后续的代码里统一用“节点数”也就是根节点深度为1这样和Leetcode、牛客上绝大多数题目的定义保持一致。为什么这个定义重要因为它决定了递归公式的写法。假设左子树深度是L右子树深度是R整棵树的深度应该是 max(L, R) 1这个“1”就是加上根节点自己。如果你把根节点那一层漏了返回值就会比正确结果小1。我见过有人写return maxDepth(root.left) maxDepth(root.right)这是把“路径长度”和“节点数量”搞混了相当于把根节点算进去又没算进去逻辑上自相矛盾。再往深一层想“深度”本质上是递归定义的一棵树的深度等于它左右子树深度的较大者加1。这个定义天然贴合二叉树的结构——每个节点最多有两个子节点所以问题可以不断分解成更小的子树。这也是为什么几乎所有二叉树题都优先用递归因为二叉树本身就是递归定义的数据结构。理解这一点你就不会只背代码而是能推导出代码。在实际工程里计算深度最常见的场景其实是“判断一棵二叉树的形状”或者“作为其他算法的子步骤”。比如在生成决策树时为了防止模型无限长下去需要限制树的深度在构建表达式树时深度影响求值的递归层数甚至在做文件目录结构抽象时目录树也可能用二叉树表示深度就代表路径嵌套层数。所以这个看似基础的题在真实的非算法场景里同样有落地价值。2. 递归解法两行代码背后的原理与代价先给出最经典的递归写法用Pythonclass TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def maxDepth(root: TreeNode) - int: if root is None: return 0 left_depth maxDepth(root.left) right_depth maxDepth(root.right) return max(left_depth, right_depth) 1这段代码的工作原理是每次调用都先处理左子树再处理右子树最后把两边结果取最大值再加1。因为先递归深入再回传结果所以这是一种后序遍历思想。调用栈的运行过程你可以想象成“下钻”从根节点一路向下遇到空节点返回0然后逐层向上带回深度。这个过程中当前路径上的节点都会压入调用栈所以空间复杂度是O(h)h是树的高度。最坏情况是树退化成链表比如每个节点只有左孩子那么h就等于节点数n递归深度就是n空间复杂度O(n)。时间上每个节点都会访问一次左右子树的递归结果都要计算所以时间复杂度严格为O(n)。你可能担心重复计算有没有可能某个子树被重复访问多次在这份代码里没有因为每个节点只会被它的父节点调用一次不会出现“重叠子问题”。动态规划里常见的“重复子问题”在这里并不存在所以不用加备忘录。既然递归这么简单为什么还要讨论代价最大的问题是“调用栈溢出”。如果你在本地跑一个10万层的树Python默认的递归深度限制往往是1000直接抛RecursionError。这种极端情况在真实的算法题里不常见但在一棵严重不平衡的树上比如按有序数组插入形成的二叉搜索树高度可能达到几万甚至几十万这时候简单的递归就顶不住了。解决办法有两个方向一是改写成迭代二是把递归调用换成手动维护栈。前者我下一节讲后者其实就是模拟函数调用栈更底层的做法。再补充一个易错点写递归时容易忘记处理空节点的深度。空树深度是0而不是1因为空树没有节点。很多人为了图省事把空节点返回1这样单节点树深度会变成2显然不对。如果你用if not root: return 0单节点树会走max(0,0)1 1正确。这里有一个我觉得特别有用的自检技巧永远从最小样本出发验证。最小样本就是空树和单节点树这两个case过了递归骨架大概率是对的。另外递归解法有一种变体叫“回溯法”写法比如def maxDepth(root): ans 0 def dfs(node, depth): nonlocal ans if node is None: return ans max(ans, depth) dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 1) return ans这种写法本质上是一个先序遍历每次深入到叶子节点时更新全局最大深度。它的好处是思路直观从根节点开始带着当前深度往下走走到空节点时什么都不用做走到非空节点就试试能不能刷新答案。实际运行结果和递归后序一样也都是O(n)时间。但注意初始深度传的是1如果根节点为空这个代码会返回0还是1会返回0因为dfs根本不会执行ans保持0。这个变体在一些复杂场景下很实用比如求二叉树最小深度、判断平衡树因为你可以在遍历过程中同时记录路径信息而不仅仅是返回纯数字。递归写法还有一个容易被忽略的点返回值不一定只能是单一数值。如果你需要“深度”的同时还希望知道哪条路径最长递归就得返回结构体或者额外维护一个全局变量。我实测下来很多业务需求并不是“只要一个数字”而是“要最深的叶子节点到根节点的路径”。比如决策树的可解释性不仅要限制深度还要找出某个叶子的完整判断路径。这时候单纯的maxDepth就不够了要用带回溯的DFS把路径记录下来。所以理解递归不只是会写两行return语句而是要清楚递归的每一次调用对应树上的哪条路径以及数据如何回流。先说一个我在面试时用过的实用观点递归解法的代码和二叉树定义一样天然但如果面试官追问“这个递归的空间复杂度为什么是O(h)而不是O(n)”你最好把调用栈过程解释清楚。可以画一张调用图访问根时栈里有root访问左子树时栈里有root、left访问left的左子树时栈里有root、left、left.left……直到空节点返回后才会逐层pop。所以栈的最大深度就是当前路径的节点数也就是树高h。平衡二叉树h约等于log n斜树hn。这个解释完全可以口述不需要画图。3. 迭代解法用栈模拟递归稳扎稳打不爆栈递归虽然简洁但“函数调用栈”不可控。为了解决这个问题成熟的工程师会第一时间想到把递归改成显式栈。显式栈的深度由我们自己控制理论上可以处理比默认递归深度大得多的树。求二叉树深度的迭代方案有好几种我分别说下思路和代码。第一种思路我称之为“记录深度法”。栈里保存的格式是(node, depth)每次从栈中弹出一个节点把当前深度和全局最大值做比较然后把它的左右孩子连同“孩子深度 当前深度 1”一起压栈。这样遍历完整棵树后全局最大值就是深度。为什么这么写有效因为我们把每个节点所在的深度都显式存了下来不需要函数调用栈去维持层级关系每次访问节点时都知道它第几层。等所有节点访问完最深的那个节点深度就是答案。def maxDepth_iter_stack(root) - int: if root is None: 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)因为栈里可能同时在很多节点平均情况下是O(h)。时间复杂度同样是O(n)每个节点进出栈一次。第二种思路是“后序遍历模拟”。因为递归后序是先算左子树深度再算右子树深度最后取max1。用栈模拟时需要区分“第一次访问节点”和“左右子树都访问完”。这比记录深度法稍微复杂但好处是不用额外存depth字段。做法是栈里每个元素是一个节点同时再用一个哈希集合或者给节点打标记记录是否已经处理过左右子树。当节点是第一次遇到则压栈左子树第二次遇到则是处理完左子树回来后压栈右子树第三次遇到则是左右都处理完可以计算该节点的深度并返回给父节点。这个实现细节容易出错我见过不少人在“返回给父节点”这一步卡壳。实际上你可以不用递归返回值而是用另一个栈存储每个节点对应的深度值同步压入弹出。这样操作虽然代码长但逻辑很清晰不容易出错。不过既然记录深度法已经足够简洁我一般不会在生产代码里写复杂的后序模拟除非题目明确要求“不能修改节点结构”或者“必须用后序遍历”。面试中最常见的追问是“你不用递归能不能求深度”这时你用记录深度法就够了。它不算“纯模拟递归”而是换了个思路在显式栈上做DFS本质上和递归先序遍历一致但更可控。我还会补充一句“如果要求严格不使用额外空间还能不能用”这个问题留到下一节讲BFS后再讨论因为不用递归和栈的解法很少见。实际项目里迭代栈解法常用于“不能信任运行时递归栈”的环境。比如某些嵌入式环境函数调用栈极小或者某些语言默认栈深度很小。我曾在一次真实业务中碰到过某个XML配置被抽象成二叉树深度可能达到几千层Python递归直接报错改用栈迭代后稳定运行。这种场景下递归解法看起来优雅但真不中用。补充一个细节栈迭代时候如果同时压入左右孩子先压谁并不影响最终深度值但如果你后续还要做“左孩子优先”的路径记录那么应该先压右孩子因为栈是LIFO后压左孩子才会先弹出左孩子。这个细节不改变深度的结果但在需要输出路径时会起到决定性作用。所以建议养成习惯在栈迭代中想DFS左优先就反着压。迭代法的复杂度分析也不要想当然。虽然空间复杂度理论上最坏O(n)但实际可能比递归好因为递归的调用栈不仅包含了节点引用还包含了函数返回地址、局部变量开销更大。显式栈只存节点引用和整数内存效率更高。这也是我在生产环境偏爱迭代的原因之一。4. 层序遍历法按层数数直观且附带额外能力如果你不想碰栈还有一种几乎不会写错的方案层序遍历BFS。思路很简单用队列一层一层往下扫描每一层结束深度加1。这个思路最贴近“树的深度就是层数”这个直觉尤其适合人类心里模拟。from collections import deque def maxDepth_bfs(root) - int: if root is None: return 0 q deque([root]) depth 0 while q: depth 1 level_size len(q) for _ in range(level_size): node q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return depth关键点是level_size len(q)必须在处理本层节点前取好因为处理过程中队列会加入下一层的节点如果不缓存这个值for循环就会混入下一层节点导致深度计数错误。这个错我初学时就踩过后来形成肌肉记忆BFS遍历固定层级时先快照size再for处理。复杂度上时间O(n)空间是队列中一层的最大节点数。二叉树的最宽层出现在最后一层节点数最多约n/2满二叉树情况下所以空间复杂度O(w)w是最大宽度。这个值在最坏情况下是O(n)但平均通常优于递归栈的O(h)不一定满二叉树的最后一层节点数多达n/2而树高只有log n所以BFS空间可能比DFS大。但在“宽度小、深度大”的链式树上BFS队列最多装2个节点空间O(1)反而比递归的O(n)好很多。实际用哪种要看树的形状。层序遍历额外带来的能力非常值钱。你在计算深度的过程中同时可以知道每一层都有哪些节点这意味着你能顺手做这些事打印二叉树的层次结构、按层输出节点值、找每层最大值、统计每层节点数、判断是否为完全二叉树、实现二叉树的序列化。这些在业务中经常成组出现。我记得有一次要可视化一棵决策树需求是“按层次把节点坐标算出来”我当时就在一次BFS里同时计算了深度和每层节点索引一次遍历解决所有问题如果单纯递归求深度还要另外再遍历一遍。所以我的经验和建议是如果你需要的不只是深度还要层内信息直接用BFS如果你只需要深度而且树比较高、宽度不大用栈迭代更省内存如果你在刷题且不考虑极端情况递归最快最不容易写错。再来聊聊“不用额外空间”的可能性。二叉树的深度能不能像中序遍历那样用Morris方法得到Morris的核心是借助叶子节点的空闲指针把空间降到O(1)。但求深度不是简单的线性序遍历它需要知道每个节点距离根节点的层数而且树的形态时刻在变。网上有人用Morris配合计数法实现Morris求深度但实现极其繁琐而且容易出错。我个人的观点是工程上没必要为了省那点内存去用Morris除非是高考式面试题或者极度受限的环境。我不会推荐大家花大量时间背Morris算深度能够手写递归和BFS已经覆盖绝大多数需求。如果树不是二叉树呢比如N叉树。BFS解法改动最小节点从两个子节点变成一个children列表遍历时把所有孩子入队即可。递归解法同理深度 max(所有子节点深度) 1。这说明BFS对“层”的理解和节点个数无关只和层深度有关通用性更强。还要提醒一个BFS的变体陷阱某些题里定义的深度是“边的数量”而不是“节点数量”。如果根节点深度定义为0那么单节点树深度就是0空树也是0queue初始时depth-1还是1就容易搞混。所以在用BFS前一定先确认题目定义的0/1边界。我常用的自洽验证方法是单节点树必须返回1按节点数定义。如果代码返回了0或2边界就有问题。这个验证比看公式快得多。5. 常见问题与排查技巧实录我整理了自己在实战里遇到过的典型问题按频率从高到低列出来每个都给排查思路。第一个问题空树和单节点树的返回结果不对。原因基本是边界定义混乱。很多人递归写if not root: return 1就会把空树深度算成1。正确做法是空树返回0单节点树走递归公式得到1。自检用例maxDepth(None)应为0maxDepth(TreeNode(1))应为1。第二个问题递归报RecursionError。这个上面提过树高超过默认递归深度就会挂。排查方法不是去调sys.setrecursionlimit(1000000)那只是临时缓解。正确做法是改成迭代栈或BFS。如果你非要继续用递归可以学习函数式语言里的“希尔排序”思路不对那个不切题。总之生产环境不要依赖调大递归上限。第三个问题BFS统计深度时多算了一层。常见于把深度初始化为1又再循环里加1。比如depth 1 while q: depth 1 ...如果root非空最终深度会比正确值多1。我建议写法是深度从0开始每进入一层加1这样代码结构与“层数”一一对应不容易多算。第四个问题用栈迭代记录深度时孩子节点入栈的深度值写错。比如stack.append((node.left, depth))忘了加1。这种错误比较容易定位因为结果会恒比正确答案小1。排查时打印每个节点深度一眼就能看出问题。第五个问题树的结构不是标准二叉树而是包含跨层指针或者孩子指针为空但节点对象却带着异常值。这种在真实业务里很常见比如把数据库表抽象成树可能出现环。如果树里有环所有遍历都会死循环。排查方法是在遍历时维护一个已访问节点集合发现重复访问就报错。虽然树本质无环但脏数据会带来环这个防御性技巧非常有用。我写树的工具函数时都会默认加一个seen集合成本低却能避免线上死循环。第六个问题最小深度和最大深度混淆。最大深度是到最远叶子最小深度是到最近叶子。题目可能要求“计算二叉树的最小深度”代码变成左右子树深度分支判断如果一个子树为空另一个非空最小深度不能取0因为空子树不算叶子路径。比如左子树为空右子树有5层那么根到右子树叶子的路径才是有效路径深度是51直接min(0, 5)1会得1就错了。这个坑很经典。遇到“最大深度”时不存在这个问题因为0不影响max。但最小深度必须特殊处理。第七个问题性能优化迷思。有人觉得“递归慢”于是盲目改成迭代其实递归和迭代都是O(n)差的是常数。真正影响性能的是你为每个节点做了什么操作。比如在递归里打印日志、拷贝数组、使用全局变量加锁都会拖慢。优先分析算法复杂度再考虑常数优化。对于那些100万节点的树重点可能不是深度计算而是整棵树的构建和存储深度计算只是其中最小的一环。我把这三个主流方法的对比整理成一个速查表方案代码量时间空间是否可能爆栈额外能力递归后序最少O(n)O(h)最坏O(n)可能无栈迭代记录深度中等O(n)O(h)最坏O(n)不会栈可控可附加路径记录队列BFS中等O(n)O(w)最坏O(n/2)不会层序遍历、层内统计表格虽然不能直接指导所有场景但给了选型依据。我个人会这样决策仅在算法题中且树深度有保证时用递归其他情况默认先写BFS因为可维护性最好如果内存敏感且树很深选记录深度的栈迭代。最后分享一个调试二叉树算法时很好用的小技巧自己写一个造树函数用层序遍历数组构造二叉树数组中的空位用None占位。比如[1,2,3,None,5]表示根1、左2、右3、2的左空、2的右5。然后构造完后立刻用层序遍历打印一次看看树是不是你想要的形状。我调试深度相关代码时曾经因为造树函数写错以为算法有问题实际是树本身就没有按预期生成。这种“先用可视化确认输入再debug算法”的顺序能节省大量时间。还有一个经验不要把深度计算单独做成一个函数然后到处复制。建议封装成一个工具类比如TreeUtils.maxDepth(root)内部可以先用递归实现后续再优化成迭代。这样调用方不用关心实现。因为深度这个指标经常配合其他指标一起用比如“左右子树深度差绝对值不超过1”就是平衡树的判断标准。封装后判断平衡树时直接拿两个子树的深度相减代码干净很多。我个人在实际操作中的体会是计算二叉树深度重点不在于“写出来”而在于“解释清楚”。面试官真正想听的不是答案而是你如何分析问题、如何权衡不同解法的优劣。递归、迭代、层序这三板斧能熟练掌握再加上对边界条件的敏感这个题就再也不算题了。后续如果你继续深入研究还可以尝试用这个模板去解“二叉树的最小深度”“N叉树的最大深度”“多棵树的森林深度计算”思路几乎相同。可以说这个基础题是理解一切树结构算法的钥匙。 
长河君 · 2026/10/15 1:19:09 · 阅读 1.2k 二叉树深度怎么算？递归、迭代、层序遍历全解析
1. 先说清楚二叉树的“深度”到底是什么很多人拿到“计算二叉树的深度”这个题第一反应是“不就递归一下吗”。确实递归解法五行内搞定但如果你只在背代码遇到“为什么空树返回0”、“为什么最大深度不是左右子树深度之和”、“递归栈溢出了怎么办”这些追问时大概率会卡壳。我在实际面试和写业务代码时被这几个问题折磨过不止一次所以先把定义和心智模型聊透。二叉树的深度严格定义是从根节点到最远叶子节点的最长路径上的节点总数。注意是“节点总数”所以只有一个根节点的树深度是1而不是0。空树呢树里一个节点都没有深度自然是0。这个边界很多人一开始会混淆。另外一个容易混淆的概念是“高度”高度通常指某个节点到最远叶子节点的最长路径上的边数或节点数看具体语境而深度经常和“层数”混用。在我后续的代码里统一用“节点数”也就是根节点深度为1这样和Leetcode、牛客上绝大多数题目的定义保持一致。为什么这个定义重要因为它决定了递归公式的写法。假设左子树深度是L右子树深度是R整棵树的深度应该是 max(L, R) 1这个“1”就是加上根节点自己。如果你把根节点那一层漏了返回值就会比正确结果小1。我见过有人写return maxDepth(root.left) maxDepth(root.right)这是把“路径长度”和“节点数量”搞混了相当于把根节点算进去又没算进去逻辑上自相矛盾。再往深一层想“深度”本质上是递归定义的一棵树的深度等于它左右子树深度的较大者加1。这个定义天然贴合二叉树的结构——每个节点最多有两个子节点所以问题可以不断分解成更小的子树。这也是为什么几乎所有二叉树题都优先用递归因为二叉树本身就是递归定义的数据结构。理解这一点你就不会只背代码而是能推导出代码。在实际工程里计算深度最常见的场景其实是“判断一棵二叉树的形状”或者“作为其他算法的子步骤”。比如在生成决策树时为了防止模型无限长下去需要限制树的深度在构建表达式树时深度影响求值的递归层数甚至在做文件目录结构抽象时目录树也可能用二叉树表示深度就代表路径嵌套层数。所以这个看似基础的题在真实的非算法场景里同样有落地价值。2. 递归解法两行代码背后的原理与代价先给出最经典的递归写法用Pythonclass TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def maxDepth(root: TreeNode) - int: if root is None: return 0 left_depth maxDepth(root.left) right_depth maxDepth(root.right) return max(left_depth, right_depth) 1这段代码的工作原理是每次调用都先处理左子树再处理右子树最后把两边结果取最大值再加1。因为先递归深入再回传结果所以这是一种后序遍历思想。调用栈的运行过程你可以想象成“下钻”从根节点一路向下遇到空节点返回0然后逐层向上带回深度。这个过程中当前路径上的节点都会压入调用栈所以空间复杂度是O(h)h是树的高度。最坏情况是树退化成链表比如每个节点只有左孩子那么h就等于节点数n递归深度就是n空间复杂度O(n)。时间上每个节点都会访问一次左右子树的递归结果都要计算所以时间复杂度严格为O(n)。你可能担心重复计算有没有可能某个子树被重复访问多次在这份代码里没有因为每个节点只会被它的父节点调用一次不会出现“重叠子问题”。动态规划里常见的“重复子问题”在这里并不存在所以不用加备忘录。既然递归这么简单为什么还要讨论代价最大的问题是“调用栈溢出”。如果你在本地跑一个10万层的树Python默认的递归深度限制往往是1000直接抛RecursionError。这种极端情况在真实的算法题里不常见但在一棵严重不平衡的树上比如按有序数组插入形成的二叉搜索树高度可能达到几万甚至几十万这时候简单的递归就顶不住了。解决办法有两个方向一是改写成迭代二是把递归调用换成手动维护栈。前者我下一节讲后者其实就是模拟函数调用栈更底层的做法。再补充一个易错点写递归时容易忘记处理空节点的深度。空树深度是0而不是1因为空树没有节点。很多人为了图省事把空节点返回1这样单节点树深度会变成2显然不对。如果你用if not root: return 0单节点树会走max(0,0)1 1正确。这里有一个我觉得特别有用的自检技巧永远从最小样本出发验证。最小样本就是空树和单节点树这两个case过了递归骨架大概率是对的。另外递归解法有一种变体叫“回溯法”写法比如def maxDepth(root): ans 0 def dfs(node, depth): nonlocal ans if node is None: return ans max(ans, depth) dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 1) return ans这种写法本质上是一个先序遍历每次深入到叶子节点时更新全局最大深度。它的好处是思路直观从根节点开始带着当前深度往下走走到空节点时什么都不用做走到非空节点就试试能不能刷新答案。实际运行结果和递归后序一样也都是O(n)时间。但注意初始深度传的是1如果根节点为空这个代码会返回0还是1会返回0因为dfs根本不会执行ans保持0。这个变体在一些复杂场景下很实用比如求二叉树最小深度、判断平衡树因为你可以在遍历过程中同时记录路径信息而不仅仅是返回纯数字。递归写法还有一个容易被忽略的点返回值不一定只能是单一数值。如果你需要“深度”的同时还希望知道哪条路径最长递归就得返回结构体或者额外维护一个全局变量。我实测下来很多业务需求并不是“只要一个数字”而是“要最深的叶子节点到根节点的路径”。比如决策树的可解释性不仅要限制深度还要找出某个叶子的完整判断路径。这时候单纯的maxDepth就不够了要用带回溯的DFS把路径记录下来。所以理解递归不只是会写两行return语句而是要清楚递归的每一次调用对应树上的哪条路径以及数据如何回流。先说一个我在面试时用过的实用观点递归解法的代码和二叉树定义一样天然但如果面试官追问“这个递归的空间复杂度为什么是O(h)而不是O(n)”你最好把调用栈过程解释清楚。可以画一张调用图访问根时栈里有root访问左子树时栈里有root、left访问left的左子树时栈里有root、left、left.left……直到空节点返回后才会逐层pop。所以栈的最大深度就是当前路径的节点数也就是树高h。平衡二叉树h约等于log n斜树hn。这个解释完全可以口述不需要画图。3. 迭代解法用栈模拟递归稳扎稳打不爆栈递归虽然简洁但“函数调用栈”不可控。为了解决这个问题成熟的工程师会第一时间想到把递归改成显式栈。显式栈的深度由我们自己控制理论上可以处理比默认递归深度大得多的树。求二叉树深度的迭代方案有好几种我分别说下思路和代码。第一种思路我称之为“记录深度法”。栈里保存的格式是(node, depth)每次从栈中弹出一个节点把当前深度和全局最大值做比较然后把它的左右孩子连同“孩子深度 当前深度 1”一起压栈。这样遍历完整棵树后全局最大值就是深度。为什么这么写有效因为我们把每个节点所在的深度都显式存了下来不需要函数调用栈去维持层级关系每次访问节点时都知道它第几层。等所有节点访问完最深的那个节点深度就是答案。def maxDepth_iter_stack(root) - int: if root is None: 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)因为栈里可能同时在很多节点平均情况下是O(h)。时间复杂度同样是O(n)每个节点进出栈一次。第二种思路是“后序遍历模拟”。因为递归后序是先算左子树深度再算右子树深度最后取max1。用栈模拟时需要区分“第一次访问节点”和“左右子树都访问完”。这比记录深度法稍微复杂但好处是不用额外存depth字段。做法是栈里每个元素是一个节点同时再用一个哈希集合或者给节点打标记记录是否已经处理过左右子树。当节点是第一次遇到则压栈左子树第二次遇到则是处理完左子树回来后压栈右子树第三次遇到则是左右都处理完可以计算该节点的深度并返回给父节点。这个实现细节容易出错我见过不少人在“返回给父节点”这一步卡壳。实际上你可以不用递归返回值而是用另一个栈存储每个节点对应的深度值同步压入弹出。这样操作虽然代码长但逻辑很清晰不容易出错。不过既然记录深度法已经足够简洁我一般不会在生产代码里写复杂的后序模拟除非题目明确要求“不能修改节点结构”或者“必须用后序遍历”。面试中最常见的追问是“你不用递归能不能求深度”这时你用记录深度法就够了。它不算“纯模拟递归”而是换了个思路在显式栈上做DFS本质上和递归先序遍历一致但更可控。我还会补充一句“如果要求严格不使用额外空间还能不能用”这个问题留到下一节讲BFS后再讨论因为不用递归和栈的解法很少见。实际项目里迭代栈解法常用于“不能信任运行时递归栈”的环境。比如某些嵌入式环境函数调用栈极小或者某些语言默认栈深度很小。我曾在一次真实业务中碰到过某个XML配置被抽象成二叉树深度可能达到几千层Python递归直接报错改用栈迭代后稳定运行。这种场景下递归解法看起来优雅但真不中用。补充一个细节栈迭代时候如果同时压入左右孩子先压谁并不影响最终深度值但如果你后续还要做“左孩子优先”的路径记录那么应该先压右孩子因为栈是LIFO后压左孩子才会先弹出左孩子。这个细节不改变深度的结果但在需要输出路径时会起到决定性作用。所以建议养成习惯在栈迭代中想DFS左优先就反着压。迭代法的复杂度分析也不要想当然。虽然空间复杂度理论上最坏O(n)但实际可能比递归好因为递归的调用栈不仅包含了节点引用还包含了函数返回地址、局部变量开销更大。显式栈只存节点引用和整数内存效率更高。这也是我在生产环境偏爱迭代的原因之一。4. 层序遍历法按层数数直观且附带额外能力如果你不想碰栈还有一种几乎不会写错的方案层序遍历BFS。思路很简单用队列一层一层往下扫描每一层结束深度加1。这个思路最贴近“树的深度就是层数”这个直觉尤其适合人类心里模拟。from collections import deque def maxDepth_bfs(root) - int: if root is None: return 0 q deque([root]) depth 0 while q: depth 1 level_size len(q) for _ in range(level_size): node q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return depth关键点是level_size len(q)必须在处理本层节点前取好因为处理过程中队列会加入下一层的节点如果不缓存这个值for循环就会混入下一层节点导致深度计数错误。这个错我初学时就踩过后来形成肌肉记忆BFS遍历固定层级时先快照size再for处理。复杂度上时间O(n)空间是队列中一层的最大节点数。二叉树的最宽层出现在最后一层节点数最多约n/2满二叉树情况下所以空间复杂度O(w)w是最大宽度。这个值在最坏情况下是O(n)但平均通常优于递归栈的O(h)不一定满二叉树的最后一层节点数多达n/2而树高只有log n所以BFS空间可能比DFS大。但在“宽度小、深度大”的链式树上BFS队列最多装2个节点空间O(1)反而比递归的O(n)好很多。实际用哪种要看树的形状。层序遍历额外带来的能力非常值钱。你在计算深度的过程中同时可以知道每一层都有哪些节点这意味着你能顺手做这些事打印二叉树的层次结构、按层输出节点值、找每层最大值、统计每层节点数、判断是否为完全二叉树、实现二叉树的序列化。这些在业务中经常成组出现。我记得有一次要可视化一棵决策树需求是“按层次把节点坐标算出来”我当时就在一次BFS里同时计算了深度和每层节点索引一次遍历解决所有问题如果单纯递归求深度还要另外再遍历一遍。所以我的经验和建议是如果你需要的不只是深度还要层内信息直接用BFS如果你只需要深度而且树比较高、宽度不大用栈迭代更省内存如果你在刷题且不考虑极端情况递归最快最不容易写错。再来聊聊“不用额外空间”的可能性。二叉树的深度能不能像中序遍历那样用Morris方法得到Morris的核心是借助叶子节点的空闲指针把空间降到O(1)。但求深度不是简单的线性序遍历它需要知道每个节点距离根节点的层数而且树的形态时刻在变。网上有人用Morris配合计数法实现Morris求深度但实现极其繁琐而且容易出错。我个人的观点是工程上没必要为了省那点内存去用Morris除非是高考式面试题或者极度受限的环境。我不会推荐大家花大量时间背Morris算深度能够手写递归和BFS已经覆盖绝大多数需求。如果树不是二叉树呢比如N叉树。BFS解法改动最小节点从两个子节点变成一个children列表遍历时把所有孩子入队即可。递归解法同理深度 max(所有子节点深度) 1。这说明BFS对“层”的理解和节点个数无关只和层深度有关通用性更强。还要提醒一个BFS的变体陷阱某些题里定义的深度是“边的数量”而不是“节点数量”。如果根节点深度定义为0那么单节点树深度就是0空树也是0queue初始时depth-1还是1就容易搞混。所以在用BFS前一定先确认题目定义的0/1边界。我常用的自洽验证方法是单节点树必须返回1按节点数定义。如果代码返回了0或2边界就有问题。这个验证比看公式快得多。5. 常见问题与排查技巧实录我整理了自己在实战里遇到过的典型问题按频率从高到低列出来每个都给排查思路。第一个问题空树和单节点树的返回结果不对。原因基本是边界定义混乱。很多人递归写if not root: return 1就会把空树深度算成1。正确做法是空树返回0单节点树走递归公式得到1。自检用例maxDepth(None)应为0maxDepth(TreeNode(1))应为1。第二个问题递归报RecursionError。这个上面提过树高超过默认递归深度就会挂。排查方法不是去调sys.setrecursionlimit(1000000)那只是临时缓解。正确做法是改成迭代栈或BFS。如果你非要继续用递归可以学习函数式语言里的“希尔排序”思路不对那个不切题。总之生产环境不要依赖调大递归上限。第三个问题BFS统计深度时多算了一层。常见于把深度初始化为1又再循环里加1。比如depth 1 while q: depth 1 ...如果root非空最终深度会比正确值多1。我建议写法是深度从0开始每进入一层加1这样代码结构与“层数”一一对应不容易多算。第四个问题用栈迭代记录深度时孩子节点入栈的深度值写错。比如stack.append((node.left, depth))忘了加1。这种错误比较容易定位因为结果会恒比正确答案小1。排查时打印每个节点深度一眼就能看出问题。第五个问题树的结构不是标准二叉树而是包含跨层指针或者孩子指针为空但节点对象却带着异常值。这种在真实业务里很常见比如把数据库表抽象成树可能出现环。如果树里有环所有遍历都会死循环。排查方法是在遍历时维护一个已访问节点集合发现重复访问就报错。虽然树本质无环但脏数据会带来环这个防御性技巧非常有用。我写树的工具函数时都会默认加一个seen集合成本低却能避免线上死循环。第六个问题最小深度和最大深度混淆。最大深度是到最远叶子最小深度是到最近叶子。题目可能要求“计算二叉树的最小深度”代码变成左右子树深度分支判断如果一个子树为空另一个非空最小深度不能取0因为空子树不算叶子路径。比如左子树为空右子树有5层那么根到右子树叶子的路径才是有效路径深度是51直接min(0, 5)1会得1就错了。这个坑很经典。遇到“最大深度”时不存在这个问题因为0不影响max。但最小深度必须特殊处理。第七个问题性能优化迷思。有人觉得“递归慢”于是盲目改成迭代其实递归和迭代都是O(n)差的是常数。真正影响性能的是你为每个节点做了什么操作。比如在递归里打印日志、拷贝数组、使用全局变量加锁都会拖慢。优先分析算法复杂度再考虑常数优化。对于那些100万节点的树重点可能不是深度计算而是整棵树的构建和存储深度计算只是其中最小的一环。我把这三个主流方法的对比整理成一个速查表方案代码量时间空间是否可能爆栈额外能力递归后序最少O(n)O(h)最坏O(n)可能无栈迭代记录深度中等O(n)O(h)最坏O(n)不会栈可控可附加路径记录队列BFS中等O(n)O(w)最坏O(n/2)不会层序遍历、层内统计表格虽然不能直接指导所有场景但给了选型依据。我个人会这样决策仅在算法题中且树深度有保证时用递归其他情况默认先写BFS因为可维护性最好如果内存敏感且树很深选记录深度的栈迭代。最后分享一个调试二叉树算法时很好用的小技巧自己写一个造树函数用层序遍历数组构造二叉树数组中的空位用None占位。比如[1,2,3,None,5]表示根1、左2、右3、2的左空、2的右5。然后构造完后立刻用层序遍历打印一次看看树是不是你想要的形状。我调试深度相关代码时曾经因为造树函数写错以为算法有问题实际是树本身就没有按预期生成。这种“先用可视化确认输入再debug算法”的顺序能节省大量时间。还有一个经验不要把深度计算单独做成一个函数然后到处复制。建议封装成一个工具类比如TreeUtils.maxDepth(root)内部可以先用递归实现后续再优化成迭代。这样调用方不用关心实现。因为深度这个指标经常配合其他指标一起用比如“左右子树深度差绝对值不超过1”就是平衡树的判断标准。封装后判断平衡树时直接拿两个子树的深度相减代码干净很多。我个人在实际操作中的体会是计算二叉树深度重点不在于“写出来”而在于“解释清楚”。面试官真正想听的不是答案而是你如何分析问题、如何权衡不同解法的优劣。递归、迭代、层序这三板斧能熟练掌握再加上对边界条件的敏感这个题就再也不算题了。后续如果你继续深入研究还可以尝试用这个模板去解“二叉树的最小深度”“N叉树的最大深度”“多棵树的森林深度计算”思路几乎相同。可以说这个基础题是理解一切树结构算法的钥匙。