1. 先说清楚：二叉树的“深度”到底是什么

很多人拿到“计算二叉树的深度”这个题，第一反应是“不就递归一下吗”。确实，递归解法五行内搞定，但如果你只在背代码，遇到“为什么空树返回0”、“为什么最大深度不是左右子树深度之和”、“递归栈溢出了怎么办”这些追问时，大概率会卡壳。我在实际面试和写业务代码时，被这几个问题折磨过不止一次，所以先把定义和心智模型聊透。

二叉树的深度，严格定义是：从根节点到最远叶子节点的最长路径上的节点总数。注意是“节点总数”，所以只有一个根节点的树，深度是1，而不是0。空树呢？树里一个节点都没有，深度自然是0。这个边界很多人一开始会混淆。另外一个容易混淆的概念是“高度”：高度通常指某个节点到最远叶子节点的最长路径上的边数或节点数，看具体语境；而深度经常和“层数”混用。在我后续的代码里，统一用“节点数”，也就是根节点深度为1，这样和Leetcode、牛客上绝大多数题目的定义保持一致。

为什么这个定义重要？因为它决定了递归公式的写法。假设左子树深度是L，右子树深度是R，整棵树的深度应该是 max(L, R) + 1，这个“+1”就是加上根节点自己。如果你把根节点那一层漏了，返回值就会比正确结果小1。我见过有人写return maxDepth(root.left) + maxDepth(root.right)，这是把“路径长度”和“节点数量”搞混了，相当于把根节点算进去又没算进去，逻辑上自相矛盾。

再往深一层想，“深度”本质上是递归定义的：一棵树的深度等于它左右子树深度的较大者加1。这个定义天然贴合二叉树的结构——每个节点最多有两个子节点，所以问题可以不断分解成更小的子树。这也是为什么几乎所有二叉树题都优先用递归：因为二叉树本身就是递归定义的数据结构。理解这一点，你就不会只背代码，而是能推导出代码。

在实际工程里，计算深度最常见的场景其实是“判断一棵二叉树的形状”或者“作为其他算法的子步骤”。比如在生成决策树时，为了防止模型无限长下去，需要限制树的深度；在构建表达式树时，深度影响求值的递归层数；甚至在做文件目录结构抽象时，目录树也可能用二叉树表示，深度就代表路径嵌套层数。所以这个看似基础的题，在真实的非算法场景里同样有落地价值。

2. 递归解法：两行代码背后的原理与代价

先给出最经典的递归写法，用Python：

class TreeNode: def __init__(self, val=0, left=None, right=None): 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，斜树h=n。这个解释完全可以口述，不需要画图。

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)，每个节点进出栈一次。

第二种思路是“后序遍历模拟”。因为递归后序是先算左子树深度，再算右子树深度，最后取max+1。用栈模拟时，需要区分“第一次访问节点”和“左右子树都访问完”。这比记录深度法稍微复杂，但好处是不用额外存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，空树也是0，queue初始时depth=-1还是1就容易搞混。所以在用BFS前，一定先确认题目定义的0/1边界。我常用的自洽验证方法是：单节点树必须返回1（按节点数定义）。如果代码返回了0或2，边界就有问题。这个验证比看公式快得多。

5. 常见问题与排查技巧实录

我整理了自己在实战里遇到过的典型问题，按频率从高到低列出来，每个都给排查思路。

第一个问题：空树和单节点树的返回结果不对。原因基本是边界定义混乱。很多人递归写if not root: return 1，就会把空树深度算成1。正确做法是空树返回0，单节点树走递归公式得到1。自检用例：maxDepth(None)应为0，maxDepth(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层，那么根到右子树叶子的路径才是有效路径，深度是5+1，直接min(0, 5)+1会得1，就错了。这个坑很经典。遇到“最大深度”时不存在这个问题，因为0不影响max。但最小深度必须特殊处理。

第七个问题：性能优化迷思。有人觉得“递归慢”，于是盲目改成迭代，其实递归和迭代都是O(n)，差的是常数。真正影响性能的是你为每个节点做了什么操作。比如在递归里打印日志、拷贝数组、使用全局变量加锁，都会拖慢。优先分析算法复杂度，再考虑常数优化。对于那些100万节点的树，重点可能不是深度计算，而是整棵树的构建和存储，深度计算只是其中最小的一环。

我把这三个主流方法的对比整理成一个速查表：

表格虽然不能直接指导所有场景，但给了选型依据。我个人会这样决策：仅在算法题中且树深度有保证时用递归；其他情况默认先写BFS，因为可维护性最好；如果内存敏感且树很深，选记录深度的栈迭代。

最后分享一个调试二叉树算法时很好用的小技巧：自己写一个造树函数，用层序遍历数组构造二叉树，数组中的空位用None占位。比如[1,2,3,None,5]表示根1、左2、右3、2的左空、2的右5。然后构造完后立刻用层序遍历打印一次，看看树是不是你想要的形状。我调试深度相关代码时，曾经因为造树函数写错，以为算法有问题，实际是树本身就没有按预期生成。这种“先用可视化确认输入，再debug算法”的顺序能节省大量时间。

还有一个经验：不要把深度计算单独做成一个函数然后到处复制。建议封装成一个工具类，比如TreeUtils.maxDepth(root)，内部可以先用递归实现，后续再优化成迭代。这样调用方不用关心实现。因为深度这个指标经常配合其他指标一起用，比如“左右子树深度差绝对值不超过1”就是平衡树的判断标准。封装后判断平衡树时直接拿两个子树的深度相减，代码干净很多。

我个人在实际操作中的体会是：计算二叉树深度，重点不在于“写出来”，而在于“解释清楚”。面试官真正想听的，不是答案，而是你如何分析问题、如何权衡不同解法的优劣。递归、迭代、层序这三板斧，能熟练掌握，再加上对边界条件的敏感，这个题就再也不算题了。后续如果你继续深入研究，还可以尝试用这个模板去解“二叉树的最小深度”“N叉树的最大深度”“多棵树的森林深度计算”，思路几乎相同。可以说，这个基础题是理解一切树结构算法的钥匙。