当前位置：首页 > news >正文

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

news 2026/6/1 23:28:22

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] 输出：2

1.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 depth

BFS思路解析：

初始化队列，将根节点入队
每处理完一层节点，深度加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 # 输出：0

4.2 单节点树

root = TreeNode(1) # 输出：1

4.3 完全二叉树

# 1 # / \ # 2 3 # / \ / \ # 4 5 6 7 # 最大深度：3

4.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) != -1

5.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)