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)11。再看maxDepth(20)它先递归maxDepth(15)得到1递归maxDepth(7)得到1于是maxDepth(20)返回max(1,1)12。回到根节点左子树深度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迭代解法一秒跑完。这个案例说明递归栈溢出不是理论上的问题只要你碰到的数据足够极端它就会真实发生。递归和迭代的核心差异可以放在一张表里看对比维度递归后序迭代BFS迭代DFS栈空间复杂度O(H)H为树高O(W)W为最宽层节点数O(H)实现难度最低中等中等极端深树表现可能栈溢出稳定稳定与遍历顺序的关系后序遍历层序遍历前序遍历4. 写二叉树程序总是报运行时错误根因排查清单4.1 空指针解引用最普遍的报错来源写二叉树程序时为什么总是报运行时错误——这个问题如果只能给一个答案那就是空指针解引用。在LeetCode上最常见的报错信息长这样AttributeError: NoneType object has no attribute left出现这个报错说明你在某个root为None的节点上访问了.left或.right。二叉树题目里一个节点的左孩子或右孩子是缺失的这是正常情况不是异常。你的代码必须时刻准备处理None。这不是LeetCode独有的问题实际工程里解析JSON树结构、遍历文件系统目录树都会遇到类似的情况。我总结了一个排查顺序按这个顺序检查基本能定位90%的运行时错误递归出口是否写在了函数最前面有没有在判空之前就访问root.left进入递归的参数是否可能为None当前节点为None时函数有没有兜底迭代解法中弹栈或出队后是否先判空再访问其子节点是否对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这道题值得你反复写三遍。第一遍用递归第二遍用层序迭代第三遍尝试用前序栈迭代。写的时候不要看答案写完再对照标准解法重点检查判空顺序、返回值、边界条件这三个地方。三遍下来你对二叉树的遍历框架才算真正有了手感后面刷什么树题都不慌。最后再分享一个小技巧——刷这类题时本地准备一棵只有根节点的树和一棵空树每次写完代码先拿这两个极端用例测试能过滤掉一大半运行时错误。