二叉树最大深度全解：递归、迭代与常见运行时错误排查

1. 为什么"二叉树的最大深度"是hot100里最值得先拿下的一道题

如果你正在刷hot100，大概率已经见过这道题。104.二叉树的最大深度挂在二叉树分类下的前几道，看起来人畜无害，网上题解也是一抓一大把，但真正动笔实现的时候，不少人的第一反应是——"这不就是个递归吗？"——然后提交，报错，再提交，再报错。我见过太多人在这个"简单题"上栽跟头，栽的根本不在算法思路上，而在一些更基础、更让人窝火的地方，比如AttributeError: 'NoneType' object has no attribute 'left'，比如RecursionError，再比如结果明明本地跑得好好的，一提交就错。

先说这题本身。给定一棵二叉树，返回它的最大深度。所谓最大深度，就是从根节点到最远叶子节点的最长路径上的节点数。一棵只有根节点的树，深度是1；空树，深度是0。语义很简单，难的是用代码把它准确表达出来，并且让程序在任何边界输入下都不崩。

这个题在我眼里是hot100二叉树板块的"地基题"。它和后面的"二叉树的层序遍历""平衡二叉树""二叉树的最大路径和"都共用同一套遍历框架。你把这题的递归写法、迭代写法、边界处理彻底吃透，后面十几道树相关的题都会顺很多。反过来，如果你这道题是靠背代码混过去的，那遇到变体很容易露馅。所以这篇不是单纯给你一个答案，而是把这道题从原理到坑全部拆开讲透，包括为什么很多人"写二叉树程序时总是报运行时错误"这种经典问题，到底出在哪些环节。

2. 递归解法：三行代码背后的三个关键细节

2.1 标准后序解法，以及"为什么返回0"

先给标准答案，Python版本的递归实现：

def maxDepth(self, root: Optional[TreeNode]) -> int: if root is None: return 0 left_depth = self.maxDepth(root.left) right_depth = self.maxDepth(root.right) return max(left_depth, right_depth) + 1

这是后序遍历的天然体现。你要算一棵树的最大深度，得先知道左子树有多深、右子树有多深，然后取较大值再加1（加的是根节点自己）。很多初学者会觉得"深度"不就是一层层往下数吗？那为什么不用前序遍历，进来就depth + 1？其实也可以，但递归返回值的方式天然适合后序：先解决子问题，再合并结果。

那"为什么空节点返回0"？这个问题的答案藏在整个递归回溯的过程里。假设一棵树只有一个根节点，它的左子树是空，右子树是空。调用maxDepth(root.left)时，传入的是None，返回0。右子树同理，返回0。根节点这一层拿到两个0，取最大值0，再加1，得到1。这正好是一棵只有根节点的树的实际深度。所以空节点返回0不是拍脑袋定的，它保证了叶子节点那一层能通过max(0, 0) + 1结算出正确的1，然后再一层层往上累加。

2.2 递归出口与空指针检查：顺序错了程序就崩

写法上最常见的翻车点，就是把对空节点的访问放在递归出口之前。比如有人写：

def maxDepth(self, root: Optional[TreeNode]) -> int: if root.left is None and root.right is None: return 1 return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

这个写法在root本身为空时，第一行就直接访问root.left，抛AttributeError。更隐蔽的是，即使root非空，当一个节点只有一个孩子时，另一个孩子传进递归后依然会变成root = None，然后在下一层继续访问root.left，照样崩。

所以递归函数的第一件事，永远是检查当前节点是否存在。这个"先判空、再访问"的顺序在所有二叉树递归题里都适用，不是这道题的特例。

if root is None: return 0

这一行必须放在函数最前面，没有任何例外。

2.3 一个更精简的写法，以及它的适用范围

也有不少人用这种一行式的写法：

def maxDepth(self, root: Optional[TreeNode]) -> int: return 0 if not root else 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

这本质上是同一个逻辑，只是把出口和合并压缩在了一行里。它读起来很爽，但前提是你对not root的语义非常清楚——None、False、0、空容器都会被not判定为真，而TreeNode对象本身是Truthy的。所以只要root是None，就返回0，否则就递归。实际提交没问题，但不建议新手一上来就写这种压缩版，容易把判空逻辑和合并逻辑混在一起，调试时反而不方便。

真实项目里我倒是更推荐显式写if root is None，因为可读性更好，同事review代码时不用去猜你的意图。LeetCode刷题可以随意，但养成好习惯没有坏处。

2.4 递归过程的完整推演

拿一棵简单的树举个例子：

3 / \ 9 20 / \ 15 7

调用maxDepth(3)，先递归maxDepth(9)。9是叶子节点，它的左子树和右子树都返回0，所以maxDepth(9)返回max(0,0)+1=1。再看maxDepth(20)，它先递归maxDepth(15)得到1，递归maxDepth(7)得到1，于是maxDepth(20)返回max(1,1)+1=2。回到根节点，左子树深度1，右子树深度2，取最大值2再加1，最终返回3。

每一步的+1都是在"回到当前节点"的时候做的一次结算。整个递归过程自底向上，跟后序遍历的顺序完全一致。

3. 迭代解法：层序BFS与栈模拟DFS两条路线

3.1 层序遍历：size快照为什么不能省

递归解法虽然简洁，但有一个绕不过去的问题——Python默认递归深度限制是1000层左右。如果遇到极端的长链树（每个节点只有一个孩子，深度达到几千甚至上万），递归解法会直接抛RecursionError。这时候你需要迭代解法兜底。

层序遍历（BFS）是理解"最大深度"的另一个绝佳视角：一棵树的最大深度，恰好就是它的层数。你把根节点所在的那一层算第1层，往下逐层累加，直到队列为空，这个累加值就是最大深度。

from collections import deque def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 queue = deque([root]) depth = 0 while queue: size = len(queue) for _ in range(size): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth += 1 return depth

这个代码里最关键的细节是size = len(queue)这一行。如果省略掉，直接在while queue里popleft然后append，那么队列的长度会随着子节点的加入不断变化，一层的边界就丢了，depth的累加时机也全乱套。size的作用是把"当前层的节点数"在开始处理这一层之前快照下来，保证 for 循环只消费当前层的节点，而新加进来的下一层节点留到下一次 while 循环再处理。

我见过有人在这里写成for _ in range(len(queue))，这在 Python 里其实也能工作，因为len(queue)在 range 创建时已经固定了，但可读性不如先size = len(queue)再使用。两种写法本质一样，重要的是理解为什么需要快照。

3.2 前序DFS栈：在栈里同时存"节点和当前深度"

BFS用队列很自然，DFS也可以用栈来模拟递归。思路是：在栈里保存两个信息——节点本身，以及它所在的深度。每弹出一个节点，就尝试用它的深度更新答案，然后把它的左右孩子连同深度+1一起压栈。

def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 stack = [(root, 1)] max_depth = 0 while stack: node, depth = stack.pop() if node: max_depth = max(max_depth, depth) stack.append((node.left, depth + 1)) stack.append((node.right, depth + 1)) return max_depth

这段代码里有个容易困惑的点：压栈时没判空，而是把node.left或node.right为None的情况留到弹栈后再用if node过滤。这是刻意为之的，目的是让代码更简洁。你也可以在压栈前判空，效果一样。

还有一种基于"后序标记法"的迭代写法，用一个二元组(node, visited)模拟递归的回溯过程，这里不展开了。对这道题来说，前序栈写法已经足够清晰，而且它在思路上跟递归版本是对应的——递归版本是先算完子树再合并，这个栈版本则是每到一个节点就立刻更新深度，本质上是前序遍历。

3.3 递归vs迭代怎么选：栈溢出是真实风险

我自己的经验是：面试或刷题时首选递归，因为它逻辑清晰、写起来快，而且在hot100的常规用例下完全够用。但如果你明确知道树可能很深（题目没有明确限制深度），或者你追求绝对稳妥，那就用迭代。这也是为什么我会建议把三种写法都掌握——不是为了炫技，而是不同场景下的不同备选方案。

有一个真实的案例：去年有人在刷某道二叉树题时，本地构造了一棵深度为1500的链式树做测试，递归解法直接崩了，换成BFS迭代解法一秒跑完。这个案例说明，递归栈溢出不是理论上的问题，只要你碰到的数据足够极端，它就会真实发生。

递归和迭代的核心差异可以放在一张表里看：

4. 写二叉树程序总是报运行时错误：根因排查清单

4.1 空指针解引用：最普遍的报错来源

"写二叉树程序时为什么总是报运行时错误"——这个问题如果只能给一个答案，那就是空指针解引用。在LeetCode上最常见的报错信息长这样：

AttributeError: 'NoneType' object has no attribute 'left'

出现这个报错，说明你在某个root为None的节点上访问了.left或.right。二叉树题目里，一个节点的左孩子或右孩子是"缺失"的，这是正常情况，不是异常。你的代码必须时刻准备处理None。这不是LeetCode独有的问题，实际工程里解析JSON树结构、遍历文件系统目录树，都会遇到类似的情况。

我总结了一个排查顺序，按这个顺序检查，基本能定位90%的运行时错误：

1. 递归出口是否写在了函数最前面？有没有在判空之前就访问root.left？
2. 进入递归的参数是否可能为None？当前节点为None时，函数有没有兜底？
3. 迭代解法中，弹栈或出队后是否先判空再访问其子节点？
4. 是否对root本身就是None的情况做了处理？LeetCode的测试用例包含空树，这是铁律。

4.2 递归出口缺失与栈溢出

第二种常见报错是RecursionError: maximum recursion depth exceeded。这个报错有两种触发场景。

第一种是递归出口确实缺失，或者出口永远到达不了，导致函数无限递归。比如有人把出口写成了if root.left is None and root.right is None，对于只有一个孩子的节点，这个条件永远不满足，递归就会沿着空子树一路传下去，直到触达递归深度上限。

第二种是树本身极深。每个节点只有一个孩子，形成一条10000层的链，任何递归解法都会撞上Python的递归深度上限。这种情况不是代码逻辑错误，而是算法选择问题——该换迭代了。

Python的默认递归深度是1000，可以通过sys.setrecursionlimit()调大，但不建议在LeetCode上依赖这个技巧，判题环境不保证你能修改，而且调得过大可能导致解释器崩溃。

4.3 全局变量污染：刷题平台上的隐形炸弹

这个坑比较隐蔽，很多人刷到中后期才碰到。你在类里定义了一个self.max_depth = 0作为成员变量，然后在方法里不断更新它。本地测试时，每个test case之间是独立的，没有发现问题。但LeetCode判题时，同一个解法可能会被多次调用，成员变量不会自动重置，上一次跑case留下来的残留值会污染下一次的结果。

class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: self.ans = 0 def dfs(node, depth): if not node: return self.ans = max(self.ans, depth) dfs(node.left, depth + 1) dfs(node.right, depth + 1) dfs(root, 1) return self.ans

这个写法问题在于：如果Solution实例被复用了，self.ans不会自动归零。虽然LeetCode的maxDepth方法通常会在每次调用时被重新实例化，但养成了依赖成员变量累积结果的习惯后，早晚会在其他题目上翻车。解决办法很简单——尽量用返回值传递结果，不要用成员变量记录中间状态。实在要用，也要在方法开头手动重置。

4.4 其他隐蔽问题：返回值类型、容器缓存

还有一个容易被忽略的点：递归函数里如果漏写了return，函数会隐式返回None。然后外层做max(left_depth, right_depth)时，其中一个参数是None，要么报TypeError，要么结果完全错误。排查时注意检查每一个递归分支是否都有明确的返回值。

另外，Python里如果给递归函数加了@lru_cache做缓存，而参数是TreeNode对象，会直接报TypeError: unhashable type: 'TreeNode'。很多人第一次碰到完全摸不着头脑。functools.lru_cache要求参数可哈希，TreeNode对象没有实现__hash__，所以不能直接缓存。二叉树的动态规划题目里确实有缓存的需求，但一般缓存的是"某个节点的状态值"而不是节点本身，需要额外设计。这道题不需要缓存，但知道这个坑，以后遇到报错不至于懵。

5. 从104题向外看：二叉树的深度是一张知识网

5.1 深度计算的三个方向：直径、平衡、最近公共祖先

104题只是起点。你在hot100里会反复看到"深度"的身影，但视角各不相同。

• 第110题"平衡二叉树"：要求判断左右子树高度差是否不超过1。做法是在后序遍历的同时返回子树高度，如果某个节点的左右子树高度差大于1，就提前返回-1标记不平衡。这比先算左子树深度、再算右子树深度、再判断、再递归下一层高效，因为后者对每个节点都重复计算子树深度，时间复杂度退化到O(n^2)。
• 第543题"二叉树的直径"：直径是任意两节点间路径的最大长度，不一定经过根节点。解法思路是：对每个节点，计算"左子树深度 + 右子树深度"作为经过该节点的路径长度，然后在全局取最大值。有了104题的深度计算框架，这道题就是加一个全局变量的事。
• 第236题"最近公共祖先"：深度在这里换了个用法——先让两个节点走到同一深度，再一起向上找。这个思路在很多场景下比直接递归找祖先更直观。

你会发现，所有这些题目都在复用同一个能力：把"树的深度"这个信息在遍历过程中正确计算并传递。104题把这个能力练好，后面三题的核心逻辑一眼就能看穿。

5.2 与遍历方式的关系：前中后序在深度问题里的分工

很多人学二叉树遍历时，前中后序背得滚瓜烂熟，但遇到具体题目就不知道用哪种。深度的计算是个很好的例子：

• 后序遍历：天然适合"自底向上"算深度。先知道子树的情况，再汇总。
• 前序遍历：适合"逐层下探"的做法。进入子节点时depth + 1，到了叶子节点再更新答案。
• 中序遍历：在深度问题里几乎没有用武之地。中序的价值体现在二叉搜索树上，它能把节点按值升序输出。

搞清楚这个对应关系后，你面对的不再是"哪道题该用哪种遍历"，而是"这个问题的信息流动方向决定了该用哪种遍历"。

5.3 搜索二叉树和线索二叉树的关联：深度的边界场景

热搜词里还提到了搜索二叉树和线索二叉树，这里也说两句。搜索二叉树（BST）的深度直接关系查找效率，一棵平衡的BST，查找复杂度是O(log n)，但如果退化成链，就变成O(n)。很多工程场景里用的红黑树、AVL树，本质上都是在控制树的深度不要失控。这和104题有同一个核心——深度是衡量树结构好坏的关键指标。至于线索二叉树，它通过利用空指针域存储前驱和后继节点信息，让遍历可以不用栈也不需要递归。但它优化的目标是遍历，不是深度计算。如果你在实现了线索化的树上算深度，要注意线索指针可能会干扰正常的子节点判断，遍历逻辑需要特殊处理，否则容易死循环。

5.4 hot100刷题顺序的个人建议

最后聊点实际的。hot100里二叉树相关的题目大约有十几道，我建议的顺序是：先做104最大深度和102层序遍历，这两个是最基础的遍历框架题；然后做110平衡二叉树和543直径，它们直接复用深度的计算逻辑；再做226翻转二叉树和101对称二叉树，这两个考察的是"镜像递归"的思维；之后是236最近公共祖先这类需要综合理解的题。这样一步步来，每道题都是前一道题的自然延伸，不会突然断层。

我个人在实际操作中的体会是：104这道题值得你反复写三遍。第一遍用递归；第二遍用层序迭代；第三遍尝试用前序栈迭代。写的时候不要看答案，写完再对照标准解法，重点检查判空顺序、返回值、边界条件这三个地方。三遍下来，你对二叉树的遍历框架才算真正有了手感，后面刷什么树题都不慌。最后再分享一个小技巧——刷这类题时，本地准备一棵只有根节点的树和一棵空树，每次写完代码先拿这两个极端用例测试，能过滤掉一大半运行时错误。