好的，我们这次来详细讲解 LeetCode 第 104 题「二叉树的最大深度」。
这是一道非常经典的二叉树题目，也是理解递归和深度优先搜索（DFS）的入门必做题。

1. 题目描述

题目链接：104. Maximum Depth of Binary Tree

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

示例：
给定二叉树 [3,9,20,null,null,15,7]：

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3。

2. 题意理解

• 叶子节点：没有左右子节点的节点。
• 深度：从根节点到该节点所经过的边的数量（或节点数，取决于定义，本题是节点数）。
• 最大深度：所有叶子节点中，从根到该叶子节点路径上的节点数最大值。

注意：

• 如果树为空（root == null），深度为 0。
• 如果只有一个根节点，深度为 1。

3. 思路分析

3.1 递归思路（自顶向下思考）

最大深度可以分解为子问题：

• 二叉树的最大深度 = 1 + max(左子树的最大深度, 右子树的最大深度)
• 递归终止条件：如果当前节点为 null，返回深度 0。

递归函数定义：
maxDepth(root) 返回以 root 为根节点的二叉树的最大深度。

递归关系：

maxDepth(root) = 0, if root == null
maxDepth(root) = 1 + max(maxDepth(root.left), maxDepth(root.right)), otherwise

3.2 为什么这样分解？

因为二叉树具有递归结构：

• 根节点的深度是 1。
• 左子树和右子树的最大深度可以递归求出。
• 整棵树的最大深度 = 1（根节点自己）加上左右子树中深度更大的那个。

4. 递归解法步骤

我们一步步模拟示例树 [3,9,20,null,null,15,7] 的计算过程。

树结构：

节点 3 (深度 1)
  左子节点 9 (深度 2)
  右子节点 20 (深度 2)
      左子节点 15 (深度 3)
      右子节点 7 (深度 3)

递归过程：

1. maxDepth(3)：
   左子树 maxDepth(9)，右子树 maxDepth(20)
   结果 = 1 + max(左子树深度, 右子树深度)

2. maxDepth(9)：
   左子树 maxDepth(null) = 0
   右子树 maxDepth(null) = 0
   结果 = 1 + max(0, 0) = 1

3. maxDepth(20)：
   左子树 maxDepth(15)，右子树 maxDepth(7)
   结果 = 1 + max(左深度, 右深度)

4. maxDepth(15)：
   左右子树都为 null，返回 1

5. maxDepth(7)：
   左右子树都为 null，返回 1

6. 回到 maxDepth(20)：
   1 + max(1, 1) = 2

7. 回到 maxDepth(3)：
   1 + max(1, 2) = 3

最终结果：3。

5. 代码实现（递归）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        return 1 + max(left_depth, right_depth)

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

6. 迭代解法（BFS 层序遍历）

除了递归，我们还可以用广度优先搜索（BFS）按层遍历，记录层数。

思路：

1. 如果根节点为空，返回 0。
2. 使用队列进行层序遍历。
3. 每遍历一层，深度加 1。
4. 遍历完所有层后，返回深度。

步骤（同样以示例树为例）：

• 初始化：队列 = [3]，深度 = 0
• 第 1 层：队列长度 = 1，深度 = 1，弹出 3，加入 9 和 20 → 队列 = [9, 20]
• 第 2 层：队列长度 = 2，深度 = 2，弹出 9（无子节点），弹出 20，加入 15 和 7 → 队列 = [15, 7]
• 第 3 层：队列长度 = 2，深度 = 3，弹出 15（无子节点），弹出 7（无子节点） → 队列空
• 结束，返回深度 3。

代码实现（BFS）：

from collections import deque

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue = deque([root])
        depth = 0
        while queue:
            depth += 1
            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)
        return depth

时间复杂度：O(n)
空间复杂度：O(n)（最坏情况队列存储节点数）

7. 总结

• 递归：代码简洁，直接利用二叉树定义，分治求解。
• BFS：直观按层计数，适合理解层次遍历。
• 关键点：空树深度为 0，单节点深度为 1，递归公式 1 + max(left_depth, right_depth)。

这道题是理解树递归的基础，很多二叉树问题都基于这种分治思想。