二叉树的最大深度LeetCode 104是力扣hot100题里的常客不管你在刷题清单里看到的是第135题还是其他编号它的本质都一样给定一棵二叉树的根节点root返回这棵树的最大深度。最大深度指的是从根节点到最远叶子节点的最长路径上的节点数。这道题能被收进热门榜不是因为它难而是因为它足够“底子厚”既能帮你建立二叉树递归的心智模型又是后面无数复杂题目的起点。无论是刚入门数据结构的新手还是准备大厂面试的老手都值得花点时间把这道题从头到尾吃透。我刷力扣刷了几年回头看这道题它最大的意义不是让你记住一行递归代码而是让你理解“树的深度”这个最基本的度量指标是怎么一步步算出来的递归怎么拆解、迭代怎么模拟、空树怎么处理、极端情况怎么防爆栈。把这些搞明白你就等于拿到了二叉树系列题目的第一把钥匙。1. 这道题为什么值得刷真正理解二叉树最大深度1.1 题目到底在问什么先看一个最经典的例子输入数组形式是这样表示的[3, 9, 20, null, null, 15, 7]对应的二叉树结构是根节点3左孩子是9右孩子是209没有左右孩子20的左孩子是15右孩子是7这棵树的深度是3路径是3 - 20 - 15或3 - 20 - 7。为什么是3而不是2因为题目里说的深度是从根节点到最远叶子节点的“节点总数”根节点自己算第1层。所以只有一个根节点的树深度是1空树深度是0。这里有一个很多新手会踩到的理解误区数组里的null不是数值而是表示“这个位置没有节点”。力扣的测试程序会自动把这个数组转换成二叉树对象你写的函数直接接收root节点即可不需要自己解析数组。如果你把null当成0去构造节点后面所有判断都会错。1.2 面试和工程中的实际价值为什么这么简单的一道题会出现在 hot100 里因为它的身影遍布二叉树各类问题。先说算法本身很多看起来高级的题目最后都要借助“深度计算”来解题。比如判断一棵树是否是平衡二叉树需要比较左右子树的高度差求二叉树直径需要把每个节点的左子树深度和右子树深度加起来取最大值求二叉树的最小深度本质上也是在遍历深度只是遇到叶子节点就要记录。再说工程场景。我参与过的前端项目里需要计算 DOM 树的嵌套层级这其实就是一棵 DOM 树的深度在文件系统里目录的嵌套深度也可以用同样思路计算数据库的 B 树高度直接影响查询 IO 次数理解树的深度能帮助你判断索引层级。虽然实际工作里不会真的让你写一个maxDepth函数去跑生产数据但“自顶向下拆解问题、递归计算子结果”的思想到处都在用。所以这道题不是刷完就扔的“水题”它是你后面做543 二叉树的直径、110 平衡二叉树、111 二叉树的最小深度、226 翻转二叉树等一堆题的基础。把这些套路吃透比盲目刷 50 道新题管用得多。2. 递归解法一行代码背后的递归逻辑2.1 递推关系怎么拆先想一个最简单的问题如果我知道左子树的最大深度是L右子树的最大深度是R那么整棵树的最大深度是多少答案很直接max(L, R) 1。这里的1是当前根节点这一层。你可以把树想象成公司组织架构根节点是总经理左子树是一个部门右子树是另一个部门。总经理自己算一层然后看两个部门哪个层级更深取较大的那个再加上总经理这一层就是整个公司的层级数。这个类比能帮你理解“递归为什么是取最大值加一”。那么左子树的最大深度怎么算完全同理左子树又分成它的左子树和右子树继续取最大值加一。这样一直拆下去拆到什么时候停拆到一个节点没有左右孩子也就是叶子节点。叶子节点没有子树它的左右子树深度都是0所以叶子节点的深度就是max(0, 0) 1 1。再往下拆会碰到空节点空节点没有深度返回0。这个0就是递归的终止条件。把递推关系写成公式就是maxDepth(root) 0 若 root 为空 maxDepth(root) max(maxDepth(root.left), maxDepth(root.right)) 1 否则这个公式是整个解法的灵魂。你不需要去背代码只要记住这个关系代码自然写得出来。2.2 代码实现与执行过程模拟递归解法在 Python 里写出来只有三行def maxDepth(root): if not root: return 0 return max(maxDepth(root.left), maxDepth(root.right)) 1代码短不代表可以掉以轻心。我见过很多人在面试时写这道题会犯两个典型错误一是忘记写空节点返回0导致访问root.left时出现NoneType报错二是把返回值写成maxDepth(root.left) 1这种形式结果只朝一个方向走根本不算另一棵子树。记住这一行return里必须同时计算左右两个子问题再取最大值最后加一。我们拿前面的例子[3, 9, 20, null, null, 15, 7]完整推演一遍递归过程调用maxDepth(节点3)节点3非空需要先算左子树和右子树深度。调用maxDepth(节点9)节点9是叶子左右都是空所以maxDepth(left)返回0maxDepth(right)返回0节点9返回max(0, 0) 1 1。节点3的左子树深度得到1接着算右子树深度调用maxDepth(节点20)。节点20非空继续算它的左子树maxDepth(节点15)返回1再算右子树maxDepth(节点7)返回1节点20返回max(1, 1) 1 2。节点3的左子树深度是1右子树深度是2返回max(1, 2) 1 3。这个推演过程看起来很简单但如果你用“递归调用栈”的视角再看一遍会有更深的体会。我习惯把每一次调用写成一张表当前节点左子树深度右子树深度返回值节点9001节点15001节点7001节点201来自151来自72节点31来自92来自203递归的本质是“函数调用自己”就像你一层一层往地底挖井挖到最深处触底之后再一层一层往回填土。每一步的返回值都会被上一层调用用到。这个过程就是后序遍历先处理完左右孩子最后才处理当前节点。复杂度方面每个节点都被访问一次时间复杂度是O(n)n为节点总数。空间复杂度在递归情况下是O(h)h是树的高度因为递归调用栈最多同时保存从根到叶子一整条路径上的调用。最坏情况树退化成链表空间是O(n)最好情况完全平衡空间是O(log n)。2.3 递归的“三步法”心法如果你刚开始刷题看到递归就头晕我建议不要直接默写代码而是每次都用固定套路去拆第一步明确终止条件。空节点返回0这一步必须先写好。第二步明确返回值含义。当前函数返回的是“以这个节点为根的子树的最大深度”。第三步明确本级要做什么。拿到左右子树的深度后取较大值再加一作为当前节点深度返回。这个三步法我后来用到了几乎所有二叉树递归题上效果非常好。比如求“翻转二叉树”终止条件是空节点返回 None返回值是翻转后的根节点本级要做的是交换左右孩子并递归处理子树。套路是通用的关键是你学会了吗。3. 非递归解法BFS层数和DFS栈迭代不少人觉得这道题用递归就够了没必要写迭代。但如果你在面试里能把非递归写法也讲出来会是一个明显的加分项。更重要的是当树的高度非常大时递归可能直接爆栈而迭代写法稳定可控。所以迭代解法不是“可有可无的补充”而是一个必须掌握的备选方案。3.1 BFS按层统计最直观既然要求的是“最大深度”那可以直接用广度优先搜索BFS一层一层往下数。每遍历完一层深度加一直到队列为空。这个思路和“数楼层”一模一样你站在一楼往下看每走完一层楼层计数加一。Python 里用collections.deque实现队列比较方便from collections import deque def maxDepth(root): if not root: return 0 queue deque([root]) depth 0 while queue: depth 1 for _ in range(len(queue)): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depth这里有一个非常关键的细节for _ in range(len(queue))一定要在循环前固定当前层的节点数量。如果直接写for node in queue然后在循环里往 queue 添加子节点就会导致遍历队列时长度不断变化不仅多处理节点还可能打乱层级边界。我见过很多人的 BFS 层序遍历写错就是栽在这个地方。为什么每次进入while循环就depth 1因为此时队列里存放的是某一层的全部节点。比如根节点初始入队队列长度是 1进入第一轮whiledepth变成 1然后处理完这一层的所有节点此时只有根节点下一层的节点已经在刚才处理过程中入队了。第二轮while再进入时队列长度正好是第二层的节点数depth再加一。这样就保证每轮循环对应一层。BFS 的空间复杂度是O(w)w是树的最大宽度。最坏情况下完全二叉树最后一层有约n/2个节点所以空间复杂度是O(n)。时间复杂度依然是O(n)。3.2 栈模拟递归的迭代写法如果你不想用 BFS也可以借助栈模拟递归过程。方法是用一个栈保存(节点, 当前深度)然后不断弹出节点更新最大深度。这本质上是一个先序遍历的变体遇到一个节点就把它的左右孩子带上下一个深度压入栈最后记录的ans就是最大深度。代码长这样def maxDepth(root): if not root: return 0 stack [(root, 1)] ans 0 while stack: node, depth stack.pop() ans max(ans, depth) if node.left: stack.append((node.left, depth 1)) if node.right: stack.append((node.right, depth 1)) return ans这个写法不需要递归调用栈而是用显式栈记住“当前走到第几层”。弹出节点时如果它的左右孩子存在就把孩子和depth 1压入栈。因为栈是后进先出所以它会先处理最后压入的节点但不管先处理左还是右都不影响最终ans的计算因为我们只是更新最大值。对比一下这种迭代 DFS 的可读性比递归差一些但它有两个实际好处一是不会因为递归层数太深触发系统栈溢出二是你可以在迭代过程中更容易地携带“路径深度、和、父节点状态”等额外信息日后做很多变体题时能直接用得上。3.3 两种迭代方式怎么选BFS 和 DFS 都行但适用场景不同。我做题的经验是维度BFS 层序遍历DFS 栈迭代实现复杂度较低按层逻辑清晰稍高需要维护节点深度空间复杂度最坏 O(n)与树宽有关最坏 O(n)与树高有关是否便于求深度很自然每层加一需要显式记录深度延伸题型层序遍历、每层最大值、锯齿形遍历路径总和、二叉树直径、最近公共祖先防止递归爆栈能有效避免能有效避免如果只是为了解这道题BFS 可能更容易理解。但如果你想通过这道题把二叉树迭代基础打牢建议两种都写一遍。真正面试的时候优先讲递归因为代码简洁、思路清晰然后补一句“如果树很高我会用迭代栈或 BFS 避免递归栈溢出”这个回答就完整了。我个人在刷题时会刻意训练自己“递归思路想清楚迭代代码写一遍”的习惯。因为很多二叉树题目的递归解法非常短但如果你只背递归遇到需要状态回溯的题目就会手足无措。提前把栈迭代的思路练熟后面再遇到前序、中序、后序遍历的迭代写法时会顺很多。4. 刷题现场运行时错误的常见原因与排查思路看热搜词里有“写二叉树程序时为什么总是报运行时错误”这确实是新手刷题特别头疼的问题。明明代码看起来没问题一提交就是Runtime Error或者RecursionError。下面我把自己踩过的坑和帮别人排查的经验整理一下。4.1 最常见的空指针与空树处理运行时错误里出现频率最高的一种就是访问了空节点的属性。比如新手喜欢写if root.left is None: return 0如果此时root本身是None那么root.left这一行就会直接抛AttributeError。Python 的报错信息通常长这样AttributeError: NoneType object has no attribute left排查方法很明确在访问任何节点字段之前先确保当前节点不为空。对于这个题目最优做法是直接写if not root: return 0而不是先判断左右孩子。还有一个容易被忽视的场景力扣给的输入可能是空树也就是root为None。如果你在函数开头没有处理空树任何递归调用都会出问题。这里有个小细节if not root在 Python 中不仅匹配None还匹配False、0、空字符串等但 TreeNode 实例不会与这些值冲突所以可以放心使用。如果你觉得不直观写成if root is None也没问题效果一样。4.2 递归深度过大导致的栈溢出另一个常见运行时错误是RecursionError: maximum recursion depth exceeded。为什么会这样因为 Python 默认的递归深度限制大概是 1000 层。如果二叉树退化成一个“链”每个节点只有一个孩子树的高度就是节点数量比如有 10001 个节点递归深度就是 10001此时就会爆栈。看一个极端例子1 \ 2 \ 3 \ 4这棵树的递归调用会一层层往下压每到一个节点都要先等待它的右子树返回结果直到最后一个节点才开始逐层返回。如果节点数量超过 Python 递归限制程序直接崩溃。解决办法有几种把递归改成迭代用栈或队列就不会受递归深度限制。设置sys.setrecursionlimit(20000)但这只是治标不治本只是把限制调大如果树再高还是会崩。在力扣刷题时测试数据通常不会设计成 1000 层所以递归很多时候能过。但面试时如果面试官故意追问“如果树特别深怎么办”你一定要能说出迭代方案。我一直觉得底层原理比“过了这道题”更重要。你能解释清楚递归爆栈的根因面试官对你的好感度会比单纯 AC 高很多。4.3 力扣在线评测的输入输出细节还有一批人代码逻辑没问题但提交后直接Compile Error或者TypeError多半是没有看清力扣的函数签名和输入定义。104. 二叉树的最大深度在力扣上的 Python 函数签名一般是# Definition for a binary tree node. class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def maxDepth(self, root: Optional[TreeNode]) - int:注意几点你不需要自行处理输入数组到二叉树的转换力扣后台会构造好root。返回值是int不要在里面print中间过程除非是在本地调试。空树返回0这个边界必须单独考虑。如果使用from collections import deque要放在外面作为导入不要写在函数内部虽然不报错但不够规范。另外力扣提交后如果出现TypeError: NoneType object is not callable通常是你把变量名root和函数名写重了或者不小心给某个局部变量赋成了None后还去调用它。我建议刷题时保持每个函数职责单一命名不要用list、dict、sum这些内置函数名尽量避免一些低级错误。最后还有一个常见误区以为数组[3,9,20,null,null,15,7]中的null表示值为 0。这会导致你误以为叶子节点深度计算错误最后算出来的深度比真实值大。记住这里的null是字面意义上的“没有节点”不是数值 0。5. 复盘总结这类题还能怎么延伸做一道题如果能连出三道变体这题就没有白刷。二叉树的最大深度是基础中的基础下面几个常见的延伸方向我在刷题和学习时都实际碰到过。5.1 从最大深度到平衡二叉树力扣 110 题“平衡二叉树”定义是每个节点的左右子树高度差绝对值不超过 1。你很容易想到用最大深度辅助解决对于每个节点分别求左子树深度和右子树深度然后判断差值是否大于 1再递归检查左右子树是否平衡。def isBalanced(root): if not root: return True left_h maxDepth(root.left) right_h maxDepth(root.right) if abs(left_h - right_h) 1: return False return isBalanced(root.left) and isBalanced(root.right)这个写法能 AC但不够好。因为它会让每个节点都被重复遍历多次maxDepth本身要递归一次isBalanced又递归一次时间复杂度退化到O(n^2)。更优的做法是在递归求深度的过程中同时判断是否平衡如果不平衡就返回-1这样每个节点只遍历一次。第一次看到这个优化思路时我才真正理解“一次递归同时做两件事”的价值。5.2 从深度到最小深度和直径最小深度是力扣 111 题它和最大深度长得像但有个坑最小深度是指从根节点到最近叶子节点的最短路径上的节点数。如果一个节点只有左孩子没有右孩子那么它的“右子树深度为 0”并不能参与最小值计算因为空节点不是叶子。正确写法要额外判断def minDepth(root): if not root: return 0 if not root.left: return minDepth(root.right) 1 if not root.right: return minDepth(root.left) 1 return min(minDepth(root.left), minDepth(root.right)) 1再看“二叉树的直径”力扣 543 题。直径是任意两个节点之间路径上边的数量或节点数减一它不一定经过根节点。计算思路是对每个节点把左子树深度和右子树深度相加然后取全局最大值。理解了最大深度直径的解法也就顺理成章了。延伸题和最大深度的关系核心坑点110 平衡二叉树判断左右子树深度差注意重复计算优化成 -1 剪枝111 最小深度求左右子树深度的最小值单子树节点不能取 0 参与最小值543 二叉树的直径左右子树深度之和最大路径不一定经过根节点5.3 最后分享一个小技巧刷二叉树类的题目多了我总结出一个特别管用的习惯先写“空节点如何处理”再写“当前节点需要从子树拿什么信息”最后写“拿到信息后怎么组合返回”。这个顺序能解决 90% 的二叉树递归题。比如最大深度空节点返回 0当前节点从左右子树拿它们各自的深度拿到后取最大值加一返回。再比如平衡二叉树空节点返回 0或 -1当前节点从左右子树拿高度拿到后比较差值如果大于 1 就返回 -1 标记不平衡否则返回高度。整个过程都是同一个套路。我在实际刷题时还喜欢在本地用打印的方式观察递归过程。比如在函数开头加一行print(visit, root.val if root else None)然后跑一个小样例。这样你能直观看到递归访问节点的顺序理解“先访问左子树再访问右子树最后处理根节点”的后序遍历结构。等理解透了再把打印语句删掉提交会非常流畅。二叉树的最大深度这道题你说它简单确实简单到只有几行代码但你说它没营养就错了。它就像算法的“九九乘法表”背起来容易真正理解透了后面遇到千变万化的二叉树题目才能稳扎稳打地推出答案。刷题不需要追求数量把一道经典题在多个方向上想明白比囫囵吞枣刷十道题更有收获。