二叉树的最大深度问题

题目描述
给定一个二叉树的根节点 root，返回其最大深度（即从根节点到最远叶子节点的最长路径上的节点数）。

解题思路
二叉树的最大深度可以通过递归或迭代两种方式求解。递归方法更简洁，迭代方法（如层序遍历）更直观。下面我们详细讲解这两种方法。

方法一：递归（深度优先搜索，DFS）

核心思想
二叉树的最大深度可以分解为：

1. 根节点的深度为 1。
2. 左子树的最大深度。
3. 右子树的最大深度。
   最终，根节点的最大深度 = 1 + max(左子树最大深度, 右子树最大深度)。

步骤分解

1. 基准情况：如果根节点为空（即树为空），返回深度 0。
2. 递归计算左子树深度：对左子节点调用同一函数。
3. 递归计算右子树深度：对右子节点调用同一函数。
4. 合并结果：返回 1 + max(左子树深度, 右子树深度)。

示例代码（Python）

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 为树的高度，递归栈的深度。

方法二：迭代（广度优先搜索，BFS）

核心思想
使用层序遍历（BFS），每遍历一层，深度加 1，直到所有节点遍历完毕。

步骤分解

1. 如果根节点为空，直接返回 0。
2. 初始化队列（包含根节点）和深度计数器 depth = 0。
3. 当队列不为空时：
   • 当前层的节点数 = 队列长度。
   • 依次弹出当前层的所有节点，并将它们的子节点加入队列。
   • 深度计数器加 1。
4. 返回深度计数器。

示例代码（Python）

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(w)，其中 w 为树的最大宽度（队列长度）。

总结

• 递归方法代码简洁，适合理解分治思想。
• 迭代方法避免了递归栈溢出的风险，适合深度较大的树。
• 两种方法均需掌握，面试中可根据面试官要求灵活选择。