1. 拿到这道题先别急着递归先聊聊它到底在考什么LeetCode Hot 100里面的题说实话不是每一道都值得精刷但二叉树的最大深度绝对值得。它排在第三十六题题号104属于你看题目列表一眼扫过去觉得这题我会但真到面试手写的时候很多人却栽在了一些莫名其妙的地方。这道题的核心考点不是怎么求深度而是三件事递归思想扎不扎实、遍历框架熟不熟、能不能随手写出非递归版本。面试官问这道题往往不是想看你背没背过答案而是想通过这棵树看看你对栈、对递归调用过程、对层序思想的理解到了哪个层次。先给没刷过这道题的朋友说清楚题目到底在问什么给你一棵二叉树求它的最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点数。比如一棵只有根节点的树深度是1空树深度是0。就这么简单的一句话却可以引申出递归DFS、迭代BFS层序、迭代DFS栈模拟、N叉树版本、变体题直径、平衡树、最小深度……一整套二叉树的题目泛化体系。我在实际刷题和带新人复盘的时候经常说一句话**二叉树的最大深度是二叉树的hello world它简单到可以在一分钟内写出来但真正理解它的人后面写路径和、建树、序列化这些题都会顺很多。**如果只是把它当一个背递归模板的题目刷过去那你这道题算是白刷了。这篇文章我不打算只贴一个递归答案然后说完事我会把递归的每一步走栈过程拆开给你看再把迭代写法为什么要这么写讲明白最后把和它相关的变体以及我在实战中常遇到的运行时错误一并梳理掉。保证看完之后你不仅能AC这一题还能顺手把一串二叉树题都打通。2. 递归解法不是背模板关键在理解递归栈的返回过程2.1 自底向上的思考方式是递归解法的灵魂求二叉树的最大深度最经典的写法就是那个三行代码def maxDepth(root): if root is None: return 0 return 1 max(maxDepth(root.left), maxDepth(root.right))很多教程把这段代码当作标准答案甩出来然后说递归嘛就是不断往下走。如果你也这么理解那大概率是似懂非懂的。因为这段代码的精髓不在往下走而在往上返回。必须要搞清楚递归函数不是一条路走到黑而是走到底之后逐层往上带回来结果。以一棵最简单的三层树为例1 / \ 2 3 / \ 4 5从根节点1开始调用maxDepth(1)要等maxDepth(2)和maxDepth(3)都返回之后才能算1 max(...)。于是走到节点2调用maxDepth(2)又要等maxDepth(4)和maxDepth(5)。走到节点4它的左右都是空直接返回0于是节点4的深度 1 max(0, 0) 1。节点5同理返回1节点2的深度 1 max(1, 1) 2。节点3是叶子节点返回1于是根节点1的深度 1 max(2, 1) 3。注意最大值是在返回的过程中一层一层比出来的不是算出来的。1 max(...)这一步看起来简单但它的含义是当前节点这一层贡献1个深度然后从左右子树的深度中挑一个更大的继续向上提交。我在给新手复盘的时候最好用的一个类比是**递归就像公司里从底层往上汇报工作。**叶子节点是基层员工他们跟主管说我这边深度是1主管把自己的1加上跟高层说我这边是2高层再把两个下属提供的数值中大的那个加上自己这一层如实汇报。整个过程没有一个人需要知道整棵树长什么样每个人只需要管好自己这一层和自己的孩子传上来的结果。2.2 递归终止条件的边界感空节点返回0为什么是对的很多人在写递归的时候总会在终止条件上犹豫到底是if root is None: return 0还是if root.left is None and root.right is None: return 1这两种写法在结果上往往一样但在逻辑上完全不同。我建议统一用空节点返回0这个版本原因有两个第一空节点返回0更符合数学上的递推定义。深度公式是f(node) 1 max(f(left), f(right))如果叶子节点的左右孩子都不存在那它们各自的f应该为0叶子节点才算成1。这样推导链是连续完整的不需要单独为叶子节点开特例。第二代码更简洁不容易漏判。如果你写只有左右都为空才返回1那在处理只有一个子树的节点时还得小心翼翼。比如一个节点只有右子树你要是没处理好空指针分分钟给你抛个AttributeError这恰恰是很多人写二叉树程序时总是报运行时错误的一大来源。你可以把空节点理解成一栋楼的负一层——它不是不存在而是深度为0的默认起点。每次从父节点下来先站在负一层然后往上爬一层才算到了父节点本身。2.3 递归的时间复杂度和空间复杂度面试必问不要卡壳这道题虽然简单但面试官顺手就会追问一句复杂度是多少。别小看这个问题答不上来很减分。时间复杂度每个节点都被访问一次每个节点只做常数级别的比较和加法所以是O(n)n是节点总数。空间复杂度递归调用的深度取决于树的高度h最坏情况下是退化链表一条线h等于n最好情况下平衡树h等于log n。空间复杂度从这个意义上说是O(h)准确说最坏O(n)。有一个非常容易误解的点空间复杂度不是指开了一个数组存结果而是系统调用栈的深度。递归每往下走一层就要在栈上压一帧保存当前函数的局部信息和返回地址。树越深栈上堆积的帧越多。这也是我们接下来要说的运行时错误出现的重要原因。3. 为什么总是报运行时错误——递归被栈溢出打倒的真相3.1 从运行时错误到Stack Overflow到底发生了什么标题相关热词里有一条特别扎眼写二叉树程序时为什么总是报运行时错误。这真的是二叉树新手绕不开的坎。我自己见过太多人代码逻辑看起来完全正确一提交就报Runtime Error心态直接炸掉。运行时错误的原因有很多种但放到最大深度这道题里最常见的元凶就是递归深度过大导致的栈溢出。这里需要澄清一个概念LeetCode的判题环境里虽然题目给定的二叉树通常不会深到几万层但你自己构造测试数据的时候完全可能造出一棵深度几万层的退化树。这时候用递归写法程序就会一路往深处递归每一层调用都要占用一部分调用栈内存直到栈空间耗尽程序崩溃。在Python里还有另一层隐患Python默认的递归深度限制大约是1000层即便你的系统栈没有爆Python解释器自己也会先抛出RecursionError: maximum recursion depth exceeded。我在本地跑极端用例时专门验证过一棵深度为1500左右的链表式二叉树递归版本必挂。这在Java里通常表现为StackOverflowErrorC里直接段错误各语言表现不同但本质都一样函数调用有栈帧成本深度太大就是扛不住。3.2 一个真实翻车的排查过程你应该也遇到过我记忆里特别深的一个案例某次刷题活动一个朋友代码写得干干净净递归版maxDepth本地测试普通的树也完全正常但一提交LeetCode就报运行时错误。他第一反应是我代码哪里访问了空节点然后各种加判空、加日志折腾半天毫无进展。我看了一眼他的测试代码问题不在maxDepth函数本身而在他额外写了一个二叉树构建函数用来从数组还原树。他为了测试极端情况造了一条长度一万的链条然后直接调用maxDepth——递归一路扎到底栈就爆了。这个过程总结起来很经典构建了一个深度为10000的链表式二叉树调用递归版maxDepth函数开始逐层压栈压到第1000层左右时Python直接抛RecursionError看上去像是某种运行时错误其实和题目本身一点关系都没有。排查结论不是算法写错了是递归这种实现方式在极端输入下有物理极限。这也直接引出了迭代写法的必要性。3.3 头和尾都要小心空指针、整数溢出很少被认真对待除了栈溢出二叉树题目里还有一个非常典型的运行时错误来源在构建测试用例时对空节点处理不当。比如用数组表示二叉树像[3,9,20,None,None,15,7]这种格式如果你没有正确把None跳过而是试图对这个节点调用root.left立刻就是空指针异常。另外关于数的大小这道题的深度最大值等于节点数正常题目给的范围不会超过几万所以不会出现整数溢出。但如果你在变体题里做路径总和或者最大路径和那就得小心累加值超出int范围了。在这道题上重点还是栈溢出和空指针这两个坎。再补一个很多人忽略的细节递归函数的返回值类型要统一。你在写Python时可能觉得不写类型注解无所谓但如果所有分支返回值表达不一致比如有的返回bool、有的返回int调用方拿到结果做max()比较时会非常痛苦。我建议从一开始就坚持写类型注解Optional[TreeNode]参数配int返回值。4. 迭代解法用BFS层序把深度变成层数顺便告别栈溢出4.1 BFS层序遍历的直观逻辑数一数有几层楼递归DFS是一条路走到黑再回头而BFS则是一层一层扫。如果把二叉树想象成一栋楼BFS就是逐层清点每层有多少个房间每扫完一层深度加1直到扫完整栋楼。用Python写BFS版最大深度非常模板化from collections import deque def maxDepth(root): if root is None: return 0 q deque([root]) depth 0 while q: size len(q) for _ in range(size): node q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) depth 1 return depth注意这行size len(q)——很多新手会问为什么要先取size不能直接while q然后popleft吗因为这里必须保证当前这一层完整出队之后深度才加1。如果你不锁定size直接用for node in q这种写法动态变化的长度会干扰层与层的边界深度就乱套了。这个BFS版的优势很明显空间复杂度最坏O(w)w是树的最大宽度在二叉树里最大宽度大约n/2但相比递归的O(h)在极端链表树下反而是优势完全没有递归栈溢出的风险因为用的是显式队列不依赖系统调用栈它的代码结构几乎是层序遍历模板后面做**二叉树的最小深度、层序遍历输出二维数组、右视图**这些题直接复用性价比极高。4.2 另一种迭代路径DFS手动维护栈思路更接近于模拟递归BFS解法直观但有些场景比如既要深度又要路径信息BFS就不够灵活了。这时候可以自己用栈模拟递归的DFS。核心思路是显式地在栈里存两个信息——当前节点和当前节点对应的深度每次弹出时比较并更新最大深度。def maxDepth(root): 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这个版本为什么正确我们每一次从栈里弹出节点时它身上带着的depth就是从根到它的路径长度。当一个节点没有左右孩子或者左右孩子都被处理完后它就是当前这条路径的末端此时用它的depth去刷新max_depth即可。用栈模拟递归还有一个额外好处你想收集路径时可以在栈里再多存一个path列表比如二叉树的所有路径那道题就是在这个模板上加了路径收集而已。所以花十分钟把这个栈版本吃透是值得的它是后面一系列DFS迭代题的基础。4.3 BFS和DFS版本如何取舍面试现场的建议如果在面试中遇到这道题我的建议是先说递归DFS代码最短逻辑最清晰面试官听了也放心——这是我会递归的信号然后主动补充如果树的深度特别大递归会有栈溢出风险我可以改成BFS或栈模拟DFS——这是我懂底层的信号面试官大概率会接着问那你写一下BFS吧你直接交出上面的deque版本这就是我实战能力在线的信号。这三个信号递进递推一道Easy题也能面出Medium的效果。很多候选人就是栽在只背了递归答案面试官追问一句递归会不会爆栈当场哑火——这一题直接就从刷过变没刷过。5. 从最大深度延伸出去变体题是真正的提分点5.1 二叉树的直径、平衡二叉树、最小深度和最大深度有什么关系最大深度这道题的延伸范围比我见过的大多数入门题都要广。把它刷透之后下面这三道题能顺出七成思路第一道二叉树的直径LeetCode 543。直径定义是任意两节点间路径上最多的节点数或边数核心思路是在递归求深度的过程中顺便记录左深度 右深度的最大值。也就是说最大深度解的递归框架加一个全局变量就变成了直径题。第二道平衡二叉树LeetCode 110。判断一棵树是不是高度平衡的本质上是要求每个节点的左右子树深度差不超过1。你可以在递归返回深度的同时检查左右子树返回的深度是否相差超过1一旦出现就标记false。它甚至不需要额外遍历一次——一次递归同时完成求深度和做判断。第三道二叉树的最小深度LeetCode 111。这道题是经典的看似很简单实际有坑。很多人直接把max改成min就交了结果发现对于根节点只有右子树这种树1 min(0, right_depth)会直接算出1——错得离谱。最小深度必须找从根到最近叶子节点的路径长度空节点不能当作叶子节点来凑数。在这里BFS层序反而是更优解因为层序遍历找到的第一个叶子节点所在的层就是最小深度一旦遇到叶子直接返回不需要遍历完整棵树。5.2 N叉树的最大深度从二叉树到多叉树的思维迁移LeetCode上有个变体是N叉树的最大深度题号559思路几乎一样只是子树从left/right变成了children数组。对于递归解法把max(maxDepth(left), maxDepth(right))换成对children列表遍历取最大值即可BFS层序更是完全一样连层内循环都不用改只是入队的从最多两个节点变成多个节点。很多人在这一步卡住其实不是不会写而是思维没转过来——仍然死守着root.left和root.right两个字段。只要意识到树形结构的关键是子节点集合N叉树版本和二叉树版本几乎没有区别。5.3 用求深度统一框架串起一系列题我的刷题顺序建议我个人比较推荐的刷题路线是104 二叉树的最大深度——理解递归返回值和DFS/BFS框架111 二叉树的最小深度——理解边界条件的陷阱BFS先找到叶子即返回110 平衡二叉树——理解递归里同时做计算和判断543 二叉树的直径——理解全局变量伴随递归收集信息559 N叉树的最大深度——理解从二叉树泛化到N叉树。这五道题按顺序刷完你对树的深度类题目就会形成一张知识网。再回头去看层序遍历、右视图、路径总和你会发现很多代码结构都似曾相识。6. 本地构建二叉树避坑指南测试用例搭不对什么算法都白搭6.1 从层序数组构建二叉树常见的几个致命细节刷LeetCode的人经常遇到一个问题题目给的是形如[3,9,20,null,null,15,7]的层序数组但本地调试的时候你得自己把它还原成二叉树。很多人在这里栽跟头因为LeetCode题面里数组和树的对应关系有隐含约定null表示该位置没有节点但是还原逻辑写错一丁点构建出来的树就是歪的。我给出一个稳妥的构建模板Python版它用队列逐层填充节点def build_tree_from_list(data): if not data or data[0] is None: return None from collections import deque root TreeNode(data[0]) q deque([root]) idx 1 while idx len(data): node q.popleft() if idx len(data) and data[idx] is not None: node.left TreeNode(data[idx]) q.append(node.left) idx 1 if idx len(data) and data[idx] is not None: node.right TreeNode(data[idx]) q.append(node.right) idx 1 return root这个写法的关键点是索引idx始终只向前移动每处理一个父节点就顺序消费数组里的两个值作为其左右孩子。如果发现是None那就只跳索引不建节点。这里最容易出错的地方有两个忘记把新建的左右子节点加入队列导致后面的节点无处安放data[idx]是None时直接套TreeNode(None)然后后续访问它的left字段立刻崩。我用这个模板在本地跑了大量测试包括[1,2]、[1,None,2]、[1,2,3,None,None,4,5]等边界情况都能正确还原为对应的树结构。建议你直接收藏省得每次刷树题都重写一遍。6.2 测试链表式二叉树如何快速构造一棵深度很大的退化树如果你要测试非递归版本在深度极大的情况下的表现需要一棵一条道走到黑的退化树可以快速构造def build_skewed_tree(depth): root TreeNode(0) cur root for i in range(1, depth): cur.right TreeNode(i) cur cur.right return root这棵树没有左子树每个节点只有右孩子从根往下形成一条链。用它在本地测试时可以直观地验证一件事maxDepth递归版在depth1100时直接报RecursionError而BFS版和栈DFS版都能轻松跑到depth10000以上。这个实验我建议每个人都亲手做一次只有亲眼看到栈溢出才会对迭代写法不是炫技而是必要有深刻记忆。6.3 如何打印二叉树快速肉眼验证你的算法结果本地调试二叉树时一个特别实用的工具是写一个简单的层序打印函数def print_tree_level_order(root): if not root: print(empty tree) return q deque([root]) while q: level [] for _ in range(len(q)): node q.popleft() level.append(str(node.val) if node else #) if node: q.append(node.left) q.append(node.right) print( .join(level))能看到树的真实结构之后调试效率会翻倍。比如构建完一棵树发现深度算出来不对最直接的排查方式就是把它打出来用肉眼对照树长什么样和深度应该是什么。很多时候问题不在于算法本身而是建树时左右孩子挂错了。7. 三种语言的实现对比Python、Java、C的注意点各不相同7.1 同步给出三份核心代码附复杂度说明这道题在面试中可能被测各种语言我这里把三种最常见语言的核心解法都写一遍方便你对照。Python递归class Solution: def maxDepth(self, root: Optional[TreeNode]) - int: if root is None: return 0 return 1 max(self.maxDepth(root.left), self.maxDepth(root.right))Java递归class Solution { public int maxDepth(TreeNode root) { if (root null) return 0; return 1 Math.max(maxDepth(root.left), maxDepth(root.right)); } }C递归class Solution { public: int maxDepth(TreeNode* root) { if (!root) return 0; return 1 max(maxDepth(root-left), maxDepth(root-right)); } };三份代码的时空复杂度完全一致时间O(n)空间最坏O(n)树退化为链表时平均O(log n)平衡树。7.2 Java/C面试中被追问的细节别露怯用Java写这道题时面试官可能会问TreeNode类的定义。标准定义是public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } }这个构造器的重载其实很有讲究三个构造方法分别覆盖无参构建为了序列化框架或反射仅填值带左右孩子完整构建。你在本地测试时直接用最简单的一参数版本new TreeNode(1)就够但要知道多参数版本存在面试官可能顺手问一句。C的话重点是指针判空。root可能是空指针访问root-left之前必须先检查root本身。另外C递归返回时不存在垃圾回收压力但要注意内存泄漏问题如果是new出来的树节点测试完最好delete掉不过LeetCode判题环境不用操心这个。还有一个所有语言都通用的细节不要用全局变量记录深度然后递归累加。比如在Python里定义一个self.depth 0然后在递归里self.depth 1这是一种常见的错误思路——因为递归回退时你还要手动self.depth - 1稍有不慎就多算或少算一层。最大深度的递归式1 max(...)这种带返回值向上传递的方式才是最不容易出错的因为它天然利用函数返回值表达子问题的结果而不需要外部变量辅助。8. 写在最后这道题刷完留下什么东西才是真的赚到回到标题本身——Hot 100第三十六题二叉树的最大深度。很多人刷完之后可能只记住了一句递归就完事了。但我希望你看完这篇文章后对这道题的印象是立体的你知道了递归的每一层调用都在系统栈上留下足迹深度过大时会栈溢出你知道了BFS层序和栈模拟DFS是递归的两条替代路线而且各有适用场景你知道了从最大深度出发可以线性延伸到直径、平衡树、最小深度、N叉树深度这一整个系列你知道了本地测试二叉树时构建和打印树的工具函数比算法本身更容易翻车。我个人的实操心得很简单把这道题当作二叉树的度量尺。后面每学一个新的树算法比如Morris遍历、线段树、二叉搜索树操作我都会先问自己一句这棵树的深度在这个算法下是变大了还是变小了——这个念头就是最大深度这道题留给我的资产。如果你正准备刷Hot 100我建议不要只盯着题号进度而是每到一道题都问自己三个问题这题考什么、递归解法爆栈怎么办、变体题怎么改。能把这三个问题都回答清楚你刷一道题的效果顶别人刷三道。这道最大深度恰好就是练这三个问题的最佳起点。最后再说一句去把BFS版代码默写一遍真的比收藏这篇文章管用。