LeetCode 104. 二叉树的最大深度 详细技术解析专栏推荐LeetCode 算法实战 | 二叉树专项突破标签LeetCode、二叉树、最大深度、递归、迭代、BFS、DFS、Python、数据结构文章目录一、题目解析题干示例提示二、核心知识点二叉树深度定义三、解题思路4种方案覆盖递归与迭代四、代码实现Python版贴合指定格式含详细注释五、代码优化与复杂度分析六、常见易错点与避坑指南七、相似题目拓展二叉树深度专项八、总结本文针对 LeetCode 104. 二叉树的最大深度 一题进行全面的技术解析。从题目理解、核心知识点铺垫到4种解题思路递归2种、迭代2种推导、代码实现严格贴合题目指定格式再到优化升级、易错点总结全程贴合算法实战场景兼顾新手入门和进阶巩固代码可直接复制提交附带详细注释便于理解同时覆盖不同解题思路满足面试多样化答题需求。一、题目解析题干示例提示1.1 题干核心信息给定一个二叉树的根节点root返回其最大深度。二叉树的最大深度定义为从根节点到最远叶子节点的最长路径上的节点数。补充说明二叉树节点结构已给定题干指定格式无需自行定义只需实现maxDepth方法接收根节点root返回一个整数最大深度。关键澄清路径上的“节点数”≠“边数”例如单个节点的树最大深度为1两个节点根→子节点最大深度为2节点数为2边数为1。1.2 示例解析示例 1输入root [3,9,20,null,null,15,7] → 输出3解析二叉树结构如下层序表示3根节点深度1├── 左子树9深度2└── 右子树20深度2├── 左子树15深度3 └── 右子树7深度3最远叶子节点为15和7从根到这两个节点的路径上有3个节点因此最大深度为3。示例 2输入root [1,null,2] → 输出2解析二叉树结构如下1根节点深度1└── 右子树2深度2最远叶子节点为2路径上有2个节点最大深度为2。1.3 题目提示关键约束树中节点数目范围0 ≤ 节点数 ≤ 10⁴数据量适中所有算法均能高效运行需注意空树处理节点值范围-100 ≤ Node.val ≤ 100节点值不影响深度计算无需处理异常值输入的二叉树以层序遍历形式给出如 [3,9,20,null,null,15,7]null 表示对应位置无节点。二、核心知识点二叉树深度定义2.1 深度与高度的区别避坑关键节点的深度从根节点到该节点的路径上的节点数根节点深度为1节点的高度从该节点到最远叶子节点的路径上的节点数叶子节点高度为1二叉树的最大深度本质是根节点的高度因为根节点的高度就是从根到最远叶子的节点数。示例示例1中根节点3的高度为3即二叉树的最大深度为3节点20的高度为2节点9的高度为1。2.2 核心逻辑推导二叉树的最大深度满足递归特性若当前节点为空深度为0若当前节点非空其深度 1 左子树最大深度和右子树最大深度中的较大值。公式表示maxDepth(root) 1 max(maxDepth(root.left), maxDepth(root.right))递归终止条件root为空时返回0。三、解题思路4种方案覆盖递归与迭代本题核心是计算根节点的高度围绕这一核心提供4种解题方案涵盖递归简单易写和迭代满足进阶需求适配不同场景快速提交、面试拓展。3.1 方案1递归法基础版极简易实现核心逻辑贴合上述公式终止条件若当前节点root为空返回0空树深度为0递归计算左子树的最大深度left_depth self.maxDepth(root.left)递归计算右子树的最大深度right_depth self.maxDepth(root.right)返回当前节点的深度1 左、右子树深度的最大值1代表当前节点本身。优势代码极简逻辑清晰无需额外数据结构劣势递归深度取决于树的高度若树为斜树如所有节点只有左子树递归深度可达10⁴可能出现栈溢出Python默认递归深度约1000需注意优化。3.2 方案2递归法优化版尾递归/剪枝核心逻辑在基础递归的基础上增加“当前深度”参数避免重复计算同时缓解栈溢出风险尾递归优化Python虽不原生支持尾递归但可减少递归过程中的临时变量。定义辅助递归函数接收两个参数当前节点node、当前节点的深度current_depth终止条件若当前节点node为空返回当前深度current_depth - 1空节点不占深度递归计算左子树深度left_depth 辅助函数(node.left, current_depth 1)递归计算右子树深度right_depth 辅助函数(node.right, current_depth 1)返回左、右子树深度的最大值即为二叉树的最大深度。优势减少重复计算递归逻辑更严谨栈溢出风险低于基础递归版劣势代码稍复杂仍依赖递归栈。3.3 方案3迭代法DFS深度优先搜索核心逻辑用栈模拟递归过程栈中存储“节点当前节点深度”的元组遍历过程中记录最大深度。初始化若根节点为空返回0否则创建栈压入 (root, 1)根节点深度为1初始化最大深度max_depth 0循环条件栈不为空弹出栈顶元素当前节点node 当前深度depth更新最大深度若当前深度depth大于max_depth则更新max_depth depth压入子节点先压入右子节点因为栈是先进后出确保左子节点先被遍历贴合DFS逻辑再压入左子节点同时将深度加1重复步骤2-5直到栈为空返回max_depth。优势无递归栈溢出风险逻辑清晰贴合DFS遍历思想劣势需额外维护栈空间开销略大。3.4 方案4迭代法BFS广度优先搜索核心逻辑用队列实现层序遍历每遍历一层深度加1最终的层数即为二叉树的最大深度层序遍历的层数 最大深度。初始化若根节点为空返回0否则创建队列加入根节点初始化深度depth 0循环条件队列不为空获取当前层的节点个数level_size确保遍历完当前层所有节点遍历当前层的所有节点弹出队列头部节点若有左子节点则加入队列若有右子节点则加入队列当前层遍历完毕深度加1depth 1重复步骤2-5直到队列为空返回depth。优势无递归栈溢出风险直观易懂层数即深度适合处理斜树劣势需额外维护队列空间开销与DFS相当。四、代码实现Python版贴合指定格式含详细注释严格按照题干指定的代码格式编写实现上述4种方案代码可直接复制到LeetCode提交无语法错误重点标注面试高频方案方案1、3、4。4.1 方案1递归法基础版面试快速提交递归基础版可直接提交# 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: 二叉树最大深度递归基础版 :param root: 二叉树的根节点 :return: 二叉树的最大深度整数 # 终止条件空树深度为0 if not root: return 0 # 递归计算左、右子树深度当前深度 1 左右子树深度的最大值 left_depth self.maxDepth(root.left) right_depth self.maxDepth(root.right) return 1 max(left_depth, right_depth)4.2 方案2递归法优化版减少栈溢出风险递归优化版可直接提交# 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: 二叉树最大深度递归优化版尾递归思想 :param root: 二叉树的根节点 :return: 二叉树的最大深度整数 # 辅助递归函数接收当前节点和当前深度 def helper(node, current_depth): # 终止条件空节点返回当前深度-1空节点不占深度 if not node: return current_depth - 1 # 递归计算左、右子树深度当前深度1包含当前节点 left_depth helper(node.left, current_depth 1) right_depth helper(node.right, current_depth 1) # 返回左、右子树的最大深度 return max(left_depth, right_depth) # 根节点从深度1开始计算 return helper(root, 1)4.3 方案3迭代法DFS高频面试方案迭代DFS版重点可直接提交# 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: 二叉树最大深度迭代DFS版用栈模拟递归 :param root: 二叉树的根节点 :return: 二叉树的最大深度整数 # 空树处理直接返回0 if not root: return 0 # 栈存储 (节点, 节点深度)初始压入根节点深度1 stack [(root, 1)] max_depth 0 # 遍历栈直到栈为空 while stack: # 弹出栈顶节点和其深度 node, depth stack.pop() # 更新最大深度 if depth max_depth: max_depth depth # 先压右子节点再压左子节点栈先进后出确保左子树先遍历 if node.right: stack.append((node.right, depth 1)) if node.left: stack.append((node.left, depth 1)) return max_depth4.4 方案4迭代法BFS直观易懂迭代BFS版可直接提交# 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: 二叉树最大深度迭代BFS版层序遍历层数即深度 :param root: 二叉树的根节点 :return: 二叉树的最大深度整数 # 空树处理直接返回0 if not root: return 0 # 队列存储当前层的节点初始加入根节点 from collections import deque 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) # 当前层遍历完毕深度加1 depth 1 return depth五、代码优化与复杂度分析5.1 四种算法复杂度对比算法类型时间复杂度空间复杂度优势劣势递归基础版O(n)O(h)h为树的高度代码极简逻辑清晰快速提交斜树时递归深度过大可能栈溢出递归优化版O(n)O(h)h为树的高度减少重复计算栈溢出风险降低代码稍复杂仍依赖递归栈迭代DFS版O(n)O(n)最坏情况斜树无栈溢出风险面试高频需维护栈空间开销略大迭代BFS版O(n)O(n)最坏情况满二叉树直观易懂层数即深度适合斜树需维护队列依赖collections.deque说明n为二叉树节点总数所有算法均需遍历每个节点一次时间复杂度均为O(n)h为树的高度平衡树hlogn斜树hn迭代法的空间复杂度取决于栈/队列的最大存储量斜树时DFS栈存储n个节点满二叉树时BFS队列存储n/2个节点。5.2 优化建议实战选型面试快速答题优先写递归基础版代码极简3行核心逻辑即可完成面试进阶答题面试官追问“如何避免栈溢出”优先写迭代DFS版高频考点或迭代BFS版处理大数据量节点数接近10⁴优先选迭代法DFS/BFS避免递归栈溢出追求代码简洁性选递归基础版追求逻辑严谨性选递归优化版或迭代法。六、常见易错点与避坑指南易错点1混淆“节点数”与“边数”错误将最大深度计算为“边数”例如示例1中认为根到15的边数为2返回2正确应为3避坑牢记“最大深度是路径上的节点数”根节点深度为1每向下一层深度加1而非边数加1。易错点2空树处理错误错误未判断根节点为空直接递归调用self.maxDepth(root.left)导致空指针报错避坑所有算法开头必须添加空树判断空树的最大深度为0。易错点3递归终止条件错误错误递归终止条件返回1认为空节点深度为1导致深度计算偏多避坑空节点深度为0非空节点深度 1 子树深度终止条件必须返回0。易错点4DFS迭代版子节点压栈顺序错误错误先压左子节点再压右子节点导致右子树先被遍历不影响结果但不符合DFS逻辑面试时可能被追问避坑栈是先进后出需先压右子节点再压左子节点确保左子树先遍历贴合DFS“左→右”的顺序。易错点5BFS迭代版未计算层数错误直接遍历所有节点未按层统计导致返回节点总数而非深度避坑必须获取当前层的节点个数level_size遍历完当前层后再深度加1确保层数正确。七、相似题目拓展二叉树深度专项通过以下相似题目巩固二叉树深度、高度的计算以及递归/迭代的实现思路LeetCode 111. 二叉树的最小深度与本题互补需注意叶子节点定义避免踩坑LeetCode 559. N叉树的最大深度思路迁移递归/迭代均可只需遍历所有子节点LeetCode 110. 平衡二叉树需计算每个节点的左右子树高度判断是否平衡依赖深度计算LeetCode 剑指 Offer 55 - I. 二叉树的深度与本题完全一致换题面不换考点。八、总结本题是二叉树的基础经典题核心考察二叉树深度的定义和递归/迭代两种解题思想重点掌握“根节点高度 二叉树最大深度”这一核心结论。核心收获明确“深度”与“高度”的区别避免混淆节点深度和高度的定义掌握递归法的核心逻辑1 max(左子树深度, 右子树深度)极简实现快速答题掌握迭代法DFS/BFS的实现解决递归栈溢出问题适配面试进阶需求避开常见易错点空树处理、节点数vs边数、压栈顺序提升代码健壮性。本题是二叉树专项的基础题掌握其解题思路后可快速迁移到最小深度、平衡二叉树等进阶题目中为后续复杂二叉树问题如路径总和、二叉树重构打下基础。