LeetCode 104：二叉树的最大深度 | DFS

LeetCode 104二叉树的最大深度 | DFS一、题目详解1.1 题目描述LeetCode 104二叉树的最大深度Maximum Depth of Binary Tree给定一个二叉树root返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。难度Easy示例 1输入root [3,9,20,null,null,15,7] 输出3示例 2输入root [1,null,2] 输出21.2 题目分析这是一道经典的树遍历问题可以使用深度优先搜索DFS或广度优先搜索BFS来解决。叶子节点没有子节点的节点左右子节点都为空。二、算法实现2.1 DFS递归实现def maxDepth(root): if not root: return 0 # 递归计算左右子树深度取较大值加1当前节点 left_depth maxDepth(root.left) right_depth maxDepth(root.right) return 1 max(left_depth, right_depth)递归思路解析如果当前节点为空深度为0递归计算左子树深度递归计算右子树深度当前节点的深度 1 max(左子树深度, 右子树深度)2.2 BFS实现from collections import deque def maxDepth_bfs(root): if not root: return 0 depth 0 queue deque([root]) while queue: depth 1 size len(queue) for _ in range(size): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depthBFS思路解析初始化队列将根节点入队每处理完一层节点深度加1将当前层所有节点的子节点入队重复直到队列为空2.3 迭代DFS实现使用栈def maxDepth_iterative(root): if not root: return 0 max_depth 0 stack [(root, 1)] while stack: node, depth stack.pop() max_depth max(max_depth, depth) if node.right: stack.append((node.right, depth 1)) if node.left: stack.append((node.left, depth 1)) return max_depth三、复杂度分析3.1 递归DFS时间复杂度O(n)每个节点访问一次空间复杂度O(h)递归调用栈的深度最好情况平衡树O(log n)最坏情况链式树O(n)3.2 BFS时间复杂度O(n)每个节点入队出队一次空间复杂度O(n)队列最多存储 n/2 个节点3.3 迭代DFS时间复杂度O(n)每个节点入栈出栈一次空间复杂度O(h)栈的最大深度四、边界情况讨论4.1 空树root None # 输出04.2 单节点树root TreeNode(1) # 输出14.3 完全二叉树# 1 # / \ # 2 3 # / \ / \ # 4 5 6 7 # 最大深度34.4 链式树只有左子树# 1 # / # 2 # / # 3 # 最大深度3五、相关扩展问题5.1 最小深度def minDepth(root): if not root: return 0 # 如果只有左子树 if not root.right: return 1 minDepth(root.left) # 如果只有右子树 if not root.left: return 1 minDepth(root.right) return 1 min(minDepth(root.left), minDepth(root.right))5.2 判断平衡二叉树def isBalanced(root): def check(node): if not node: return 0 left check(node.left) if left -1: return -1 right check(node.right) if right -1: return -1 if abs(left - right) 1: return -1 return 1 max(left, right) return check(root) ! -15.3 二叉树的直径def diameterOfBinaryTree(root): max_diameter 0 def depth(node): nonlocal max_diameter if not node: return 0 left depth(node.left) right depth(node.right) # 更新直径 max_diameter max(max_diameter, left right) return 1 max(left, right) depth(root) return max_diameter六、总结6.1 核心要点要点说明递归DFS代码简洁易于理解BFS使用队列按层计数迭代DFS使用栈模拟递归时间复杂度三种方法都是O(n)6.2 方法对比方法优点缺点递归DFS代码最简洁可能栈溢出极端情况BFS层次清晰空间复杂度较高迭代DFS避免栈溢出代码稍复杂6.3 扩展思考如何计算二叉树的平均深度如何找到二叉树中距离最远的两个节点最大深度问题在实际应用中有什么意义参考资料LeetCode 104 题解二叉树深度