二叉树的最大深度这题在力扣hot100题里基本是每个刷题人的必经之路也是二叉树系列里最入门的一道。但我发现一个很有意思的现象题目本身逻辑极其简单可评论区里递归栈溢出运行时错误空指针的讨论一直没断过。这恰恰说明深度这道题真正考察的不是你会不会递归而是你对树的遍历框架、递归的边界控制、以及不同解法的复杂度差异理解得够不够透。这篇东西我打算换个讲法不直接给你标准答案就完事而是把这道题背后几个容易卡壳的点全部拆开为什么有些人递归写着写着就爆栈、为什么用迭代法反而更稳、以及同一道题在不同语言里踩坑的差异。最后我会把它和连续子数组、记忆化搜索之类的题目做类比你会发现深度这个操作其实就是树结构里最通用的测量单位。1. 题目还原与递归版解题思路先看原题描述给定一个二叉树 root返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例里面通常会给一个 [3,9,20,null,null,15,7] 的层序结构期望输出是 3。这个表述在 LeetCode 上有一个特别容易误导新手的地方它说的是从根节点到最远叶子节点的最长路径上的节点数。注意是节点数而不是边的数量。你如果按边数算深度 3 的树你可能会写成深度 2然后在边界用例上卡住。更准确的理解方式是——每个节点本身贡献一个深度单位空节点贡献 0叶子节点贡献 1父节点的深度等于它两个孩子深度的较大值再加 1。递归解法按照这个理解直接翻译成代码是极其自然的。以 Python 为例def maxDepth(root): if not root: return 0 left_depth maxDepth(root.left) right_depth maxDepth(root.right) return max(left_depth, right_depth) 1这五行代码就是整个题目的灵魂。它背后的递推逻辑是一棵树的最大深度 左子树最大深度 和 右子树最大深度 的较大者加上根节点本身。这个思路看起来简单但你要是把它当成死记硬背的模板遇到变种题比如求最小深度就容易翻车。递归版的时间复杂度是 O(n)n 是节点总数因为每个节点恰好被访问一次。空间复杂度取决于树的高度最坏情况下是一个链状树递归深度会退化到 n这时候栈开销会很大。我见过很多人在这题上AC 了但觉得很虚就是因为没搞明白空间复杂度那条线。退一步说递归版本是最容易验证正确性的写法因为它直接对应数学归纳法的结构空树返回 0 是归纳基础非空树先假设左右子树的深度已知然后合并出当前树的深度。这是归纳步骤。两者齐全算法在逻辑上一定正确。2. 三种主流解法对比为什么不推荐只背一种LeetCode 讨论区里这题的题解大致分三类递归 DFS、迭代层序 BFS、以及显式栈模拟的 DFS 后序。这三种解法面试中全都被问过而且很多面试官问完递归版本会追加一句能不能不用递归写你要是只会第一种现场现想后两种就会慌。先看迭代层序 BFS。它的核心思路非常直观深度这个概念在层序遍历里天然就是我一共遍历了几层。用一个队列存放当前层的节点每处理完一整层就把深度计数器加一。Python 代码如下from collections import deque def maxDepth(root): if not root: return 0 queue deque([root]) depth 0 while queue: level_size len(queue) for _ in range(level_size): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth 1 return depth这个版本最大的优势是——它天然规避了递归深度过深的问题。对于一棵高度上万甚至十万的极端链状树递归写法很可能直接报栈溢出而 BFS 的队列内存随节点数线性增长虽然空间也是 O(n)但不存在爆发式增长的系统栈限制。另一个优势是它和后面很多题是连通的比如二叉树的右视图、层序遍历、之字形遍历解题框架完全一样你在这个基础上多做一步就能解决那一系列问题。第三种显式栈模拟 DFS 其实是递归的机械展开面试中展示你能把递归转化成就地栈操作是非常加分的。但实现细节比前两种复杂你需要在栈里同时存节点和该节点对应的深度出栈时更新最大深度。这里有个容易写错的点压栈顺序和深度值的对应关系。Python 写法如下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这个写法实质上模拟了前序遍历先访问根再先入右后入左的过程栈里每一对二元组记录的是当前这个节点在树中的真实深度。我建议你把三种解法都写一遍不是为了炫技而是为了训练同一个算法目标可以用不同数据抽象实现的思维。面试时候手撕代码你会发现很多时候卡住不是因为不会某一种解法而是因为你只背了模板一旦被追问边界情况就不知道改哪里。三种方式的时间和空间复杂度对比我整理成一个表格解法时间复杂度空间复杂度适用场景主要风险递归 DFSO(n)O(h)h 为树高常规树、代码最简洁链状树栈溢出层序 BFSO(n)O(k)k 为最大层宽高度未知的深树空间波动宽树内存大显式栈 DFSO(n)O(h)需要自定义遍历顺序入栈元组逻辑易错你注意观察这个表空间复杂度的差异集中在最坏情况。LeetCode 官方数据里绝大多数测试样例都是常规随机生成的二叉树高度不会特别离谱所以递归版本基本都能过。但真实的编程场景里你处理的数据结构可能来自恶意构造的输入也可能来自一个递归生成的目录树高度失控是真实存在的风险。3. 为什么写着写着就报运行时错误常见崩溃原因排查标题里那个热搜词其实很扎心——写二叉树程序时为什么总是报运行时错误。这几乎是所有刷题新手都会碰到的问题。我自己帮人排查过不少这类错误原因高度集中而且每一次都是同一批问题反复出现。第一个高频原因是空指针访问。初学者拿到 root 后不判空就直取 root.val或者递归里没写终止条件。这类错误在 LeetCode 上通常会显示为 AttributeError 或空引用异常。排查方法极其简单所有引用节点属性的地方先把节点本身判空。递归函数开头第一句写 if not node: return 0 或等价逻辑基本能挡掉 70% 的运行时错误。注意这里有个容易忽略的细节递归里空节点要返回 0而不是 None。返回 None 后续执行 max(left, right) 会直接抛类型错误。第二个高频原因是递归深度爆栈。LeetCode 的 C 和 Python 对不同语言递归栈深度的限制不完全一致但 Python 默认递归深度限制在 1000 层左右。一旦树的形态接近链状递归就溢出了。这种错误报出来的往往是 RecursionError 或 Segmentation Fault。很多人在讨论区看到这段代码为什么核心用例报错十有八九都是这个原因。解决办法很简单要么调高递归限制sys.setrecursionlimit要么改用显式栈或层序 BFS。我个人的习惯是如果题目数据范围在 10^4 到 10^5 以上且树的形态未知默认优先写迭代而不是硬刚递归。第三个高频原因是逻辑遗漏具体表现是答案偶尔对偶尔不对。这类问题不在代码本身而在你如何理解最大深度的定义。比如求最大深度时有些人会在叶子判断上做文章先判断 if not root.left and not root.right然后返回 1。这逻辑在最大深度题里没有问题但冗余且容易出错。真正容易出错的是你拿最大深度的代码去改最小深度题目结果所有测试用例都差一点。最小深度必须处理只有一个孩子时空孩子不算一层的情况这和最大深度是完全不同的处理方式。第四个坑更隐蔽全局变量污染。有些人喜欢写一个全局变量 self.max_depth 0然后在递归过程中不断更新它。思路没问题但如果你定义在类外面或者没有正确初始化多个测试用例之间会互相串数据。LeetCode 的判题器会对每个测试用例实例化新的对象但如果你的全局变量定义在模块级别那么上一次测试的脏数据就会被带入下一次。这类 bug 特别难查因为本地跑单测可能全过一提交就挂在某个用例上。为了帮你彻底排除第四类问题我给你一个简单的自检方案核心递归函数里尽量不要改任何外部状态所有结果通过返回值向上传递。这是函数式风格也是 LeetCode 判题环境下最稳的写法。4. 从深度到更复杂问题的延伸同一套路在不同题型里的变化这道题虽然简单但它恰好站在一个分岔路口上。你可以从深度这个维度向右看——二叉树的直径、平衡二叉树判断、二叉树的最小深度、最大宽度、二叉树的最大路径和这些都是它的变体或近亲。先说平衡二叉树判断。它要求判断二叉树是否是高度平衡的即每个节点的左右子树高度差不超过 1。如果你会算左子树深度和右子树深度那平衡判断的直接写法就是对每个节点都计算两侧深度计算完立即做差。但这里有个性能陷阱如果每个节点上都重新递归计算子树深度时间复杂度会变成 O(n^2)。正确解法是让递归函数同时返回两个信息——当前子树是否平衡、当前子树高度。用 Python 可以返回一个元组def is_balanced(root): def check(node): if not node: return True, 0 left_balanced, left_h check(node.left) right_balanced, right_h check(node.right) balanced left_balanced and right_balanced and abs(left_h - right_h) 1 return balanced, max(left_h, right_h) 1 return check(root)[0]这个函数和 maxDepth 的差别只是在返回值里多了一个布尔值。我之前带过一个实习生他看完 maxDepth 的题解后自己花了十分钟就写出这个版本这就是把基础吃透之后举一反三的样子。再说二叉树的直径。直径定义是任意两个节点路径最长的那条路径长度用边的数量衡量。有趣的是它必须经过某个节点作为路径拐点在那个节点上左子树深度 右子树深度就是经过它的最长路径边数。所以解法依然基于深度计算但全局记录最大值。这里你需要小心一个细节路径不一定要经过根节点所以要遍历所有节点的左深加右深取最大值。def diameter_of_binary_tree(root): res 0 def depth(node): nonlocal res if not node: return 0 left depth(node.left) right depth(node.right) res max(res, left right) return max(left, right) 1 depth(root) return res这个写法里核心的 depth 函数几乎就是题目的递归模板只是额外用 res 记录路径长度。你会发现学到一个扎实的基础函数等于给十几个后续题目同时打了地基。延伸到最大宽度的时候就需要结合 BFS 的索引标记法了。宽度不是节点个数而是同一层最左和最右非空节点之间的位置差。BFS 时要给每个节点分配一个序号左孩子 2 倍索引右孩子 2 倍加一每一层记录最左最右索引差。这个框架和层序求深度的 BFS 代码几乎相差不到几行只要你之前真正理解了队列里按层处理的逻辑这个扩展就是顺势的事。再强调一个概念区分最大深度、节点数、边数这三个指标在不同题目里定义不同。最大深度题按节点数计二叉树直径按边数计最小深度题也是按节点数计。你一定要在动手写之前先看明白题目定义而不是想当然地套模板。5. 实测经验不同语言的实现差异与性能对比我常年在这道题上给同事做参考实现实测下来不同语言之间的注意点差异其实挺大的而且这些差异往往是面试官追问的素材。Python 版本最重要的坑就是递归深度限制。LeetCode 上默认的递归深度是 1000但第一次测试数据可能只有几十层你在本地测试全通过提交后突然遇到超时或栈溢出就是因为测试数据里包含了极端链状用例。建议你在 Python 里写递归时启动时加两行保护性代码import sys sys.setrecursionlimit(1000000)这算是一个防御式编程的技巧。但也别加得太大理论上递归深度受限于 C 栈Python 设到一百万只是给解释器一个许可实际能不能到那个深度取决于系统栈大小的限制。更稳的做法还是迭代法。JavaScript 版本Node.js 的递归也是有限制的。常规情况下深度超过一万也会报 Maximum call stack size exceeded。遇到这种问题我一般直接切换到迭代。迭代的时候注意 JS 没有内置队列数组的 shift() 是 O(n) 时间所以 BFS 层序处理大量节点时优先用空间换时间的方式维护一个索引指针而不是频繁 shift。更优雅的方案是手动维护一个队列数组并用 head 指针标记队首这样进出队复杂度都是 O(1)。Java 版本官方题解推荐递归。Java 的递归栈深度比 Python 宽松得多默认栈容量在 1MB 左右Release 模式下能撑到几十万层常规题目完全够用。但如果数据规模达到百万级节点且是链状分布建议用栈模拟或 BFS。Java 的 ArrayDeque 做层序 BFS 时和 Python 的 deque 行为一致很顺手。有些网上代码喜欢用 LinkedList 当队列注意 LinkedList 的 removeFirst 存在装箱拆箱开销性能略差但不影响小规模数据。C 版本的注意点在内存泄漏。这有点跑题LeetCode 判题系统本身会回收内存但如果你自己测试时反复创建节点却忘了释放长期跑本地压测会越跑越慢。在一个每次测试都 new 大量节点的工程里最好把树的销毁写清楚。另外 C 递归深度没有 Python 那么紧张但栈溢出依旧是极端输入下的真实风险迭代法依然是终极保底方案。我还想提一个有意思的性能观察在同样规模的随机树上递归 DFS 和迭代 BFS 的执行时间差异通常不超过 10%真正拉开差距的是极端数据结构。这一点正好说明了——刷题阶段的性能优化是次要的核心是保证逻辑在不同输入下都正确。你先把三种解法都吃透再去做性能调优。6. 边界条件与样例设计的经验笔记这道题的边界条件不算多但每一个都很典型。我在平时带人写二叉树相关题目时总会让他们一开始就养出一个习惯不管题目怎么问先写一个最小可用输入集合来自测。第一个边界空树。输入 root 为 null 时最大深度为 0。这看起来简单却是最容易漏的。很多人递归版本第一行 root 为空返回 0但迭代版本往往会忘记在循环开始前判空直接在 deque([root]) 这一行炸掉。处理方式是在 BFS 开头先 if not root: return 0。第二个边界单节点树。只有一个根节点时最大深度为 1。这个场景能立刻检验出你到底是按节点数还是按边数理解深度。如果你的代码在该返回 1 时返回 0大概率是结束条件写错了。第三个边界链状树。每个节点只有一个孩子左右交替甚至全部偏右。这个场景考验的是你的递归是否会爆栈、你的 BFS 空间复杂度是否符合预期。面试时你可以主动构造这样一个输入来自测。第四个边界完全二叉树。全部节点都有两个孩子或没有孩子深度应该是 log2(n1) 向上取整的结果。这个用于交叉验证你手算的深度和代码输出的深度是否匹配。我在自己写测试工具时通常会写一个简单的数组转树函数。LeetCode 风格的层序序列化格式null 代表空节点数组按层从左到右排列。自己造数据就靠这个函数把 [3,9,20,null,null,15,7] 变成一棵树。还有配套的树形状打印函数方便肉眼检查。把这些小工具沉淀下来以后你做任何二叉树题目都会快很多。另外一个我没说但很重要的小细节LeetCode 上有些历史版本的题目输入不再局限于 int 节点值而是增加了很多泛型测试。这意味着你要养成不依赖节点值本身来做判断的习惯判空永远用节点引用而不是用值是否为 null 字符串这类旁门左道。7. 从这道题反推刷题策略怎么把 easy 题刷出 hard 的效果最后借着这道题聊一点刷题方法论。二叉树的最大深度在 LeetCode 上是一道 easy 题但它的价值一点都不 easy。它身上挂着一整条知识树树的遍历前中后序、层序、分治思想、栈与队列的应用、递归到迭代的转换、以及时间空间复杂度的权衡。我建议你把这道题当做一个刷题经络图的起点。刷完这题你要确保自己伸手就能打出的不仅仅是这题的 AC 代码而是一套树问题通用工具。具体来说就是在本地建一个二叉树工具模块至少包含三个函数根据层序数组构造树、前序/中序/后序/层序的遍历框架、以及求深度/判断平衡/求直径这些基础操作。这样一来以后遇到子树、路径、根到叶等细分题型你不是从零开始而是像搭积木一样组合已有模块。只刷一题而不知其所以然过两周就忘了。但如果你在这道题上不光搞懂了递归还彻底理解了 BFS 的队列层级划分理解了显式栈里深度和节点的配对存储那你就等于同时预习完了至少五道中等难度的二叉树题。这笔试按知识点聚类、以不变应万变的最划算玩法。有个小技巧我一直很推荐刷完这题单独建一个笔记页面标题就叫二叉树的深度递归、迭代、变体。把三种解法的代码贴进去然后旁边手写备注包括每个解法的空间复杂度是怎么推导的、在链状树上会发生什么、面试官可能会追问哪些问题。坚持用这个方法记录 30 道题你的算法知识树会比其他盲目刷题的人清晰五倍以上。
