我来给你讲解 LeetCode 第 104 题：二叉树的最大深度（Maximum Depth of Binary Tree）。

题目描述

给定一个二叉树的根节点 root，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例：

输入：root = [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
输出：3

解释：最长路径是 3 → 20 → 7（或 3 → 20 → 15），包含 3 个节点。

解题思路

1. 问题理解

• 二叉树深度是从根节点到某个叶子节点所经过的 节点个数（包括根和叶子）。
• 如果树为空（root == null），深度为 0。
• 否则，最大深度 = 1 + max(左子树深度, 右子树深度)。

2. 递归思路（自顶向下 / 深度优先搜索 DFS）

• 递归函数定义：maxDepth(root) 返回以 root 为根的树的最大深度。
• 递归终止条件：如果 root 为空，返回 0。
• 递归过程：
  1. 计算左子树的最大深度 leftDepth = maxDepth(root.left)
  2. 计算右子树的最大深度 rightDepth = maxDepth(root.right)
  3. 返回 1 + max(leftDepth, rightDepth)

递归过程示例（对应示例树）：

maxDepth(3) 
  → leftDepth = maxDepth(9) 
      → 9 是叶子节点：1 + max(maxDepth(null), maxDepth(null)) = 1 + max(0,0) = 1
  → rightDepth = maxDepth(20)
      → 20 有左右孩子：
          leftDepth = maxDepth(15) = 1
          rightDepth = maxDepth(7) = 1
          → 1 + max(1,1) = 2
  → 1 + max(1, 2) = 3

代码实现（递归）：

def maxDepth(root):
    if not root:
        return 0
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    return 1 + max(left_depth, right_depth)

时间复杂度：O(n)，每个节点访问一次。
空间复杂度：O(h)，h 为树高，递归栈深度。

3. 迭代思路（广度优先搜索 BFS / 层序遍历）

• 使用队列进行层序遍历，每遍历一层，深度加 1。
• 步骤：
  1. 如果根为空，返回 0。
  2. 初始化队列，加入根节点，深度 depth = 0。
  3. 当队列不为空：
     • 当前层的节点数 = 队列长度。
     • 依次弹出当前层所有节点，并将它们的非空子节点加入队列。
     • 深度 depth++。
  4. 返回 depth。

示例树的 BFS 过程：

队列变化：
初始: [3]        depth=0 → 处理第1层后 depth=1
下一层: [9,20]   depth=1 → 处理第2层后 depth=2
下一层: [15,7]   depth=2 → 处理第3层后 depth=3
队列空，返回 depth=3

代码实现（BFS）：

from collections import deque

def maxDepth(root):
    if not root:
        return 0
    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)
        depth += 1
    return depth

时间复杂度：O(n)，每个节点入队出队一次。
空间复杂度：O(n)，最坏情况队列存储最后一层节点数（完全二叉树最后一层约 n/2 个节点）。

总结

• 递归 更简洁，符合二叉树深度的自然定义。
• 迭代（BFS） 更直观，按层计数。
• 两种方法都是 O(n) 时间，但递归空间 O(h)，BFS 空间 O(n)（最宽一层）。
• 如果树非常不平衡，递归可能栈溢出，此时 BFS 更稳定。