最近整理 LeetCode 热题100 的刷题笔记我把“二叉树的最大深度”翻出来从头到尾重做了一遍。这道题看起来短小几乎每个题解区都有但它在热题100里的地位一点都不低递归、树的遍历、边界条件这三条主线全被它串起来了。无论你是刚接触二叉树的初学者还是准备面试想快速唤醒手感的老手这道题都值得用一整个晚上把它彻底吃透。我不是要说“背下代码就完事”而是想把这几年里我反复做这道题积攒下来的理解、调试经验和周边扩展一次性写清楚。1. 为什么“最大深度”值得占热题100的一个名额1.1 一道题牵出三条主线很多人刷 LeetCode 热题100喜欢按题号从易到难硬啃。可一旦进入二叉树专题就会发现“二叉树的最大深度”几乎是最好的开胃菜。它同时覆盖了三样东西递归思想、二叉树遍历、以及空值边界判断。递归思想是树的天然表达方式一棵树的深度可以被拆成“根节点加上左右子树的深度”而这个拆法会一层层传递到叶子节点直到遇到空节点。二叉树的遍历更不必多说BFS层序遍历天然能数出深度DFS深度优先也能在进入每一层时记录深度。至于边界条件一道空树到底该返回 0 还是别的值很多人在第一次写的时候都会犹豫而这恰恰是 LeetCode 上最容易触发运行时错误的地方。在面试里这道题经常被拿来当作“热场题”。面试官先让你两分钟写个递归版本接着马上追加一句“如果树特别深递归会出问题你还能换个写法吗”这其实是在考察你是否理解递归背后的系统调用栈以及是否能够熟练切换成迭代思路。热题100把它列进去不是因为它难而是因为它能像探针一样快速暴露你对树和递归的掌握程度。1.2 从题目表述到建模深度到底是什么先统一一下我们对“深度”的定义。按 LeetCode 的标准习惯一棵只有根节点的树深度是 1空树深度是 0。根节点到最远叶子节点的路径上经过的节点个数就是这个最大深度。不少初学者会在这里犯迷糊深度和层数是不是一个东西在实际做题时大多数时候可以混用。但如果题目问“从 0 开始计数”那返回值就要跟着调整。LeetCode 这道题默认从根节点为深度 1 开始所以递归的基准情况就是空节点返回 0。动手建模时我会把一棵树想象成“套娃”。每个节点都是一个小容器容器的价值等于它自身这一层加上左右两个小容器里的最大值。这种建模方式不需要关注树的整体形状只需要相信任何一棵树都能从空节点这个最小单元开始一层层组合出结果。这就是分治思想的朴素版本。2. 递归解法先想清楚最小子问题再动手2.1 一棵树的深度等于子树深度加一递归解法最核心的一句话就是当前节点的深度 1 max(左子树深度, 右子树深度)。为什么是这个公式因为根节点本身就占据了一层而左右子树各自又是一个独立的树结构它们的深度同样可以由这个公式往下推。我自己习惯在写递归前先问三个问题基准情况是什么答节点为空深度为 0。当前层怎么处理答拿到左右子树的深度取较大者。如何向上一层返回答加上当前节点这一层即 1。这三个问题对应了递归代码的骨架。顺序不能反尤其是基准情况必须写在最前面。否则一旦出现了空节点函数就会陷入对空节点的属性访问运行时直接报NoneType object has no attribute left这类错误。2.2 用 Python 写出递归版本LeetCode 上最常见的 Python 写法def maxDepth(root): if root is None: return 0 left_depth maxDepth(root.left) right_depth maxDepth(root.right) return 1 max(left_depth, right_depth)如果你喜欢更精简的写法还可以这样def maxDepth(root): return 0 if root is None else 1 max(maxDepth(root.left), maxDepth(root.right))两种写法本质相同唯一需要留意的是在递归调用前root已经通过基准判断所以访问root.left和root.right是安全的。很多人写代码时会先写return 1 max(...)把空判断漏掉这就是最常见的运行时错误来源。用一棵具体的树走一遍流程。假设输入是[3, 9, 20, null, null, 15, 7]这是 LeetCode 官方示例里那棵经典二叉树根节点 3先递归左子树 9。节点 9 的左右孩子都为空所以maxDepth(9) 1 max(0, 0) 1。回到根节点再递归右子树 20。节点 20 有左孩子 15 和右孩子 7两个都是叶子所以maxDepth(20) 1 max(1, 1) 2。最终根节点maxDepth(3) 1 max(1, 2) 3。这个步骤看起来简单但能顺着递归调用顺序把它完整画出来才是真理解。很多报错不是语法错误而是脑子里递归顺序是乱的。2.3 递归为什么是后序形态以及复杂度分析细心的读者会发现这个递归的返回值是在左右子树都算完之后才产生的本质上是一种后序遍历先处理左子树、再处理右子树、最后处理根节点。这和“层序遍历天然一层层数”不同递归方案把深度计算变成了自底向上的过程。复杂度方面时间上每个节点恰好被访问一次所以是O(n)n 是节点总数。空间上递归会占用系统调用栈最深时的调用层数等于树的高度。如果这棵树是平衡的调用栈深度是O(log n)但如果树退化成一个只往左延伸的链表状结构调用栈深度就是O(n)。这也是为什么后续要研究迭代解法递归在极端输入下可能爆栈。LeetCode 的判题环境通常不会拿几万层的单链树来卡这道题但真实面试里面试官很可能会追问“如果树特别深怎么办”。如果你只能交出递归版本面试就可能止步于此。3. 迭代解法BFS 数层数和 DFS 带状态入栈3.1 为什么面试官会让你再写一个迭代版迭代版本的意义不是为了炫技而是为了证明你了解递归的本质。递归靠的是系统调用栈迭代则可以把栈显式地写到代码里或者用队列规避栈深度问题。我见过不少候选人递归写得飞快但只要一问“怎么不用递归”就开始支支吾吾。这说明他对递归只是背熟了模板并没有真正理解“深度优先”和“广度优先”这两种搜索框架。面试官问这道题时通常期待的迭代版有两个方向一是 BFS 层序遍历每遍历一层深度加一二是 DFS 显式栈把当前节点和当前深度一起压栈每次弹出时更新最大深度。两个方向都能达到O(n)时间但空间表现略有区别。3.2 BFS 队列版一层一层数BFS 的直觉非常直观既然深度就是层数那我们从根节点开始一层一层往外扩每处理完一层就把深度加一。from collections import deque def maxDepth(root): 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)。必须在一开始就把当前层的节点数固定下来然后只处理这些节点。如果不这样做队列里会混入下一层的节点深度计数就会乱套。我第一次写这个版本时就是因为把len(queue)写进了for循环的条件里导致每弹出一个节点长度都在变化结果深度莫名其妙多算了好几层。BFS 的空间复杂度是O(w)其中w是树的最大宽度。平衡二叉树最后一层大概有n/2个节点所以最坏情况下空间也是O(n)。这个版本的好处是它天然不会受到树高的影响即使树退化成单链队列里也始终只有一两个节点非常稳。3.3 DFS 栈版把深度当作状态压进去如果不借助系统调用栈那我们就自己维护一个栈。每个栈元素不只是节点本身还要带上该节点当前的深度。def maxDepth(root): if not root: 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这里我习惯把深度和节点打包成元组一起入栈。弹出的节点可能是右子树也可能是左子树但它所携带的depth一定是在入栈那一刻算好的互不干扰。树的高度不再依赖系统调用栈而是由我们自己定义的栈来承载只要内存足够几千层的树也能跑完。空间复杂度最坏也是O(n)和递归版本的调用栈一样。但区别在于这个栈是我们自己控制的不容易触发语言的递归深度限制对刷题环境更友好。3.4 两个迭代版本的取舍我把这两个迭代方案放在一起比较过它们的适用场景其实不太一样方案时间额外空间特点递归 DFSO(n)O(树高)最坏 O(n)写法最简洁基于系统栈BFS 队列O(n)O(树宽)最坏 O(n)层数直观适合追求最小深度DFS 显式栈O(n)O(树高)最坏 O(n)显式控制栈避免系统栈限制如果只是做这道题我会优先写递归因为它直观且不容易出错。但如果面试官追问我会转向 BFS因为“最大深度”和“层数”的概念绑定得很紧解释成本低。DFS 显式栈更适合放在“求所有路径”这类需要携带路径信息的问题里那道题里栈的显式状态会格外好用。4. 调试实训二叉树代码运行时错误的常见根源4.1 空指针对 None 乱调用 val 的典型现场“写二叉树程序时为什么总是报运行时错误”这个问题在搜索引擎里相当高频。我太熟悉这类报错了因为几乎每个初学二叉树的人都会遇到同一块绊脚石对一个空节点调用了属性。看下面这段错误代码def broken_max_depth(root): return 1 max(broken_max_depth(root.left), broken_max_depth(root.right))这函数连一个基准情况都没有。当递归走到叶子节点时root.left已经不是节点而是None。下一次调用开始时代码直接访问None.leftLeetCode 判定环境立刻抛出一个 RuntimeException。解决方法很简单就是在函数入口处把空节点拦截掉。还有一种隐蔽的空指针问题出现在 BFS 里入队前只判断了node.left和node.right但忘了判断node本身是否为None。虽然多数入队节点来自上一层非空节点的子节点但只要你曾经把None塞进队列后面几行的node.left就会在某个深夜里突然炸掉。所以我写迭代代码时习惯在入队前统一做一次非空检查。4.2 递归深度爆炸链表状二叉树与爆栈递归版在 LeetCode 的普通测试用例上通常不会出问题但如果你把代码拿到本地自己构造一棵一万层的退化成单链的树再跑一遍大概率会看到 Python 抛出的RecursionError: maximum recursion depth exceeded。这不是思路错了而是 Python 默认递归深度限制比较小通常在 1000 左右。树的深度一旦超过这个值递归调用栈直接触顶。解决方案有三个方向第一用sys.setrecursionlimit临时调高限制但这治标不治本第二改用 3.3 节里的显式栈版本第三使用 BFS 队列版本彻底绕开树高带来的栈风险。在面试现场我不会真的去调递归限制而是直接告诉面试官递归在高树场景下有爆栈风险我可以用迭代重写。这个回答本身就比代码更有价值因为它体现了对运行时机制的理解。4.3 用最小的输入完成单步推演遇到调试困难时我有个习惯动作把 LeetCode 的例子输入缩到最小然后手动模拟。比如输入[3, 9, 20, null, null, 15, 7]可以缩成[1, 2]意思是根节点 1 只有左孩子 2。用递归走一遍调用maxDepth(1)进入后判断非空继续。算左子树maxDepth(2)。maxDepth(2)的左右子树都是空返回1 max(0, 0) 1。算右子树maxDepth(None)返回 0。根节点返回1 max(1, 0) 2。这个结果符合预期只有根和左孩子深度就是 2。如果你已经变异思义地加了一行调试打印也可以观察递归进入和返回的顺序。打印语句在递归代码里是极好的“慢镜头”。但 LeetCode 判题时不能保留打印本地调试没问题提交前记得删干净。4.4 顺带检查边界值、节点顺序和左右混淆还有一种比较低级的错误是左右子树搞反。比如1 max(right, left)和1 max(left, right)在这道题里结果一样因为max是交换的。但你一旦把这道题的套路带去做“判断是否为镜像树”或者“求二叉树直径”左右顺序就会变成致命错误。所以刷题时要刻意养成“先左后右”的书写习惯不是为了这道题而是为了后续变形题不踩坑。边界值永远要单独测试空树返回 0单节点返回 1只有左子树的链状树返回树长完全二叉树按层数返回。这些用例写进自己的测试列表里每次写完树相关代码都跑一遍能省掉大量调试时间。5. 最大深度不是终点和遍历及树变体的关系5.1 层序遍历视角最大深度是 BFS 的层数如果你已经做过“二叉树的层序遍历”会发现最大深度的 BFS 版本几乎就是层序遍历的副产品。层序遍历要求把每一层单独装进一个列表输出而最大深度只需要数一数层数。两者共用同一个外层循环结构区别只在for循环结束后一个往结果数组里 append一个给depth加一。我在做热题100时会把这两道题放到同一天里刷然后用同一份 BFS 模板去套。这样做的记忆效果远比孤立刷题好得多因为大脑记住的是“结构”而不是孤立的代码碎片。层序遍历的模板一旦滚瓜烂熟后面的“二叉树的右视图”“填充每个节点的下一个右侧节点指针”都会更快上手。5.2 从最大深度延伸到平衡二叉树与直径最大深度还经常作为前置知识出现在更复杂的题里。比如“验证平衡二叉树”它要求每个节点的左右子树高度差不超过 1。最笨的办法是对每个节点都调用一次maxDepth但这样会重复访问大量节点复杂度退化成O(n log n)甚至O(n^2)。更优的解法是后序遍历一边递归一边计算子树高度同时检查平衡性一旦不平衡立刻返回 -1。再比如“二叉树的直径”直径被定义成任意两个节点路径上的最大边数。它本质上是在找“某个节点的左子树深度 右子树深度”的最大值。想明白了这一点你会发现直径和最大深度是同一条递归链上的两个变量只是一道题在累加一道题在取最大值。5.3 搜索二叉树、线索二叉树与最大深度的“血缘关系”刷题时还会看到“搜索二叉树”和“线索二叉树”这两个词。搜索二叉树BST是关于节点值有序性的变体和深度本身没关系但它同样依赖递归结构左子树所有值小于根右子树所有值大于根。如果你能把“二叉树的最大深度”的递归框架吃透再去写 BST 的插入、删除、验证会顺畅很多因为它们都遵循“先处理当前节点再递归处理子树”的模式。线索二叉树则是个更冷门的概念。它把空指针利用起来让某个节点的前驱或后继可以直接被找到。这和最大深度没有直接关系但有共同点它们都在讨论“空指针”的合理处理方式。线索二叉树把空指针变成线索最大深度把空指针当成递归边界本质都是对树结构的重新理解。所以我的建议是不要只做一个孤立的“最大深度”题解而是把这道题当作一个坐标原点向层序遍历、平衡二叉树、直径、BST 这些方向发散出去。热题100的复利就藏在这种关联里。6. 刷题与复习节奏让热题100真正产生复利6.1 按主题打包而不是按题号刷热题100最大的价值不是“一百道题做完”而是它按主题覆盖了算法面试的核心骨架。我自己的刷法是把这 100 道题按主题重排二叉树一组、链表一组、动态规划一组、二分查找一组、图论一组。二叉树这一组里“最大深度”放在第一天第二天做层序遍历第三天做验证二叉搜索树第四天做二叉树展开为链表。这种打包方式有两个好处。第一主题内的题目会反复使用同一个模型每做一道新题都在复习前面的旧题。第二一旦某道题卡住你容易定位到“是不是树遍历没吃透”还是“递归返回值的语义没想清”而不是孤立地怪自己脑子不够用。6.2 用周赛和随机题检验模式识别光在热题100里反复滚还不够我会隔三差五参加线上的周赛或者从题库里随机抽一道二叉树题。周赛还有一个作用检验模式识别能力。比如周赛里如果出现一道“求树的最小深度”你应该立刻想到 BFS 可以提前终止而不是机械套用最大深度的递归模板。最小深度和最大深度的差异非常有意思最大深度用 BFS 也可以但必须遍历到最后一层最小深度用 BFS 更优因为一旦遇到第一个叶子节点就能返回。这种对比只有在题目密度足够大时才会浮现出来。我一直觉得刷题数量不是目的题目之间的差异才是真正的学习素材。6.3 建立自己的题解备注格式我每做完一道热题100都会在笔记里写三行话核心模型、易错点、和哪些题共享相似结构。拿“二叉树的最大深度”举例我当时的笔记是核心模型后序遍历返回值表示当前子树的高度。易错点空节点必须返回 0不能访问空节点的属性。关联题目层序遍历、平衡二叉树、二叉树直径、最小深度。这种备注格式看起来很朴素但它能让三个月后的我快速恢复记忆。人脑的记忆曲线很残酷一道题做完第二天不看就会忘。与其依赖“我肯定记住了”的错觉不如花两分钟把抽象模型写下来。另外我会把题解区的高赞代码和自己的代码对照一遍。如果我写出了更精简的版本那说明我真的掌握了如果别人的代码更短而我一时看不懂我会问自己他省略了什么?这个省略是否依赖某个约定这个过程比看十遍题解都有效。写在最后如果你现在正卡在“二叉树的最大深度”这道题上我的建议很简单先把递归版本写熟再用三组测试用例验证空树、单节点、多层树然后强制自己不看题解写出 BFS 版本和显式栈版本。完成这三步后你已经吃透了这道题。剩下的时间用来做关联题去观察深度信息如何在递归返回值里流动。这道题的价值不在“AC”那一瞬间而在于它帮你打通了理解树的任督二脉。刷题多年回头看很多难题的思路起点恰恰就是这道小小热题里那行朴素的代码空节点返回 0非空节点返回 1 加上左右子树的较大深度。把这个模型刻进脑子里后面的路会顺畅许多。