问题说明（含示例）

问题描述：给定二叉树的根节点 root，返回该二叉树的最大深度。最大深度定义：从根节点到最远叶子节点的最长路径上的节点数（叶子节点指没有左、右子节点的节点）。

示例：

1. 输入：root = [3,9,20,null,null,15,7]（二叉树结构：根为 3，左子树为 9；右子树为 20，20 的左子树为 15、右子树为 7）输出：3解释：

   • 根节点 3 到叶子节点 9 的路径：3→9（2 个节点，深度 2）；
   • 根节点 3 到叶子节点 15 的路径：3→20→15（3 个节点，深度 3）；
   • 根节点 3 到叶子节点 7 的路径：3→20→7（3 个节点，深度 3）；最长路径的节点数为 3，故最大深度为 3。

2. 输入：root = [1,null,2]（二叉树结构：根为 1，无左子树；右子树为 2，2 无左、右子树）输出：2解释：

   • 根节点 1 到叶子节点 2 的路径：1→2（2 个节点），无更长路径，故最大深度为 2。

解题关键

二叉树最大深度的核心是 “计算根到最远叶子的最长路径”，主流实现方式有递归法（分治思想） 和迭代法（层序遍历 / BFS），两种方法的时间复杂度均为 O(n)（n 为节点数，每个节点访问一次），空间复杂度因树的结构而异。

1. 递归法（分治思想）核心思路

• 终止条件：当前节点为 null（空树或子树为空，深度为 0）；
• 分治逻辑：
  1. 递归计算当前节点左子树的最大深度；
  2. 递归计算当前节点右子树的最大深度；
  3. 整棵树的最大深度 = 左、右子树最大深度的最大值 + 1（“+1” 是因为要包含当前节点本身）。

2. 迭代法（层序遍历）核心思路

• 用队列（Queue） 实现层序遍历（按 “层” 访问节点），利用队列 “先进先出（FIFO）” 特性，每遍历完一层，深度加 1；
• 步骤：
  1. 若根节点为空，返回深度 0；
  2. 初始化队列，将根节点入队，深度初始化为 0；
  3. 循环：若队列不为空，记录当前层的节点总数（避免后续节点干扰），遍历当前层所有节点，将其左、右子节点（非空）入队，遍历完一层后深度加 1；
  4. 循环结束，深度即为最大深度。

对应代码

方法 1：递归法（简洁高效）

from typing import Optional

# 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:
        # 终止条件：空节点深度为0
        if not root:
            return 0
        # 分治：左子树深度 vs 右子树深度，取max后+1（包含当前节点）
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        return max(left_depth, right_depth) + 1

示例理解

我们用 示例 1 的二叉树（root = [3,9,20,null,null,15,7]）来拆解递归函数的执行过程，这个树的结构如下（便于理解）：

• 根节点：3（左子节点是9，右子节点是20）
• 节点9：叶子节点（左、右子节点都是null）
• 节点20：左子节点是15，右子节点是7（15和7都是叶子节点）

递归的核心是 “先深入到最底层（叶子节点），再回溯计算深度”，我们按调用顺序逐步拆解：

1）调用根节点的maxDepth(3)

计算以3为根的树的最大深度，需要先算它的左子树（9）和右子树（20）的深度。

2) 计算左子树深度：调用maxDepth(9)

进入maxDepth(9)函数：

• 判断9是否为空？否（root是9，非null）。
• 先算9的左子树深度：调用maxDepth(9.left)（9.left是null）。
  • 进入maxDepth(null)：触发终止条件if not root，返回0（左子树深度为 0）。
• 再算9的右子树深度：调用maxDepth(9.right)（9.right是null）。
  • 同样触发终止条件，返回0（右子树深度为 0）。
• 计算9的深度：max(0, 0) + 1 = 1（+1是因为包含9本身）。
• 所以maxDepth(9)返回1，即根节点3的左子树深度是1。

3)计算右子树深度：调用maxDepth(20)

进入maxDepth(20)函数：

• 判断20是否为空？否。
• 先算20的左子树深度：调用maxDepth(15)（15是叶子节点）。
  • 进入maxDepth(15)：
    • 算15.left（null）：返回0；算15.right（null）：返回0。
    • 15的深度：max(0, 0) + 1 = 1，所以maxDepth(15)返回1。
• 再算20的右子树深度：调用maxDepth(7)（7是叶子节点）。
  • 同理，maxDepth(7)返回1（右子树深度为 1）。
• 计算20的深度：max(1, 1) + 1 = 2（包含20本身）。
• 所以maxDepth(20)返回2，即根节点3的右子树深度是2。

4)计算根节点3的深度

根节点3的左子树深度是1，右子树深度是2：

• 深度 = max(1, 2) + 1 = 3（+1是因为包含3本身）。
• 最终maxDepth(3)返回3，和示例 1 的输出一致。

方法 2：迭代法（层序遍历）

from typing import Optional
from collections import deque  # 用deque实现队列，popleft效率更高

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 not root:
            return 0
        
        depth = 0
        queue = deque([root])  # 初始化队列，根节点入队
        
        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)
            # 遍历完一层，深度加1
            depth += 1
        
        return depth

对应的基础知识

实现最大深度计算需掌握以下基础概念与操作：

1. 二叉树节点结构

• TreeNode 类包含 val（节点值）、left（左子节点指针）、right（右子节点指针），二叉树的深度计算依赖对 left 和 right 的递归 / 迭代访问。

2. 递归的核心要素

• 终止条件：if not root: return 0（空节点无深度，避免无限递归）；
• 分治思想：将 “整棵树的深度” 拆分为 “左子树深度” 和 “右子树深度” 两个子问题，通过递归求解子问题后合并结果（max(...) + 1）。

3. 队列的基础操作

• 迭代法用 collections.deque 实现队列（list 的 pop(0) 效率低，deque.popleft() 为 O(1)）；
• 核心操作：queue.append(node)（节点入队）、queue.popleft()（队首节点出队），通过 “记录当前层节点数” 确保每轮循环只处理一层节点。

4. max() 函数与条件判断

• 递归法中 max(left_depth, right_depth) 取左、右子树深度的最大值，是合并子问题结果的关键；
• if not root 处理空树边界 case，避免后续操作报错（如访问 root.left）。

对应的进阶知识

最大深度计算涉及二叉树遍历的深层逻辑与复杂度分析：

1. 递归的时间与空间复杂度

• 时间复杂度：O(n)，每个节点会被递归函数访问一次（计算左、右子树深度时各访问一次，总次数与节点数成正比）；
• 空间复杂度：O(h)（h 为树的高度），递归依赖 “函数调用栈”，栈帧数量等于树的高度：
  • 平衡树（如满二叉树）：h = log n，空间复杂度 O(log n)；
  • 斜树（所有节点只有左 / 右子树）：h = n，空间复杂度 O(n)（最坏情况）。

2. 迭代法（层序遍历）的复杂度

• 时间复杂度：O(n)，每个节点入队、出队各一次，总操作次数为 2n，渐进复杂度 O(n)；
• 空间复杂度：O(n)，队列最多存储 “当前层的所有节点”，最坏情况为满二叉树的最后一层（节点数约 n/2），故空间复杂度 O(n)。

3. 分治思想的应用

• 分治思想是递归法的核心：将 “大问题（整棵树深度）” 拆解为 “小问题（左 / 右子树深度）”，求解小问题后通过简单运算（取 max 加 1）合并结果；
• 该思想可扩展到其他二叉树问题（如求二叉树的最小深度、直径等），是处理树形结构的常用思路。

4. DFS 与 BFS 的区别

• 递归法本质是深度优先搜索（DFS）：优先深入左 / 右子树，直到叶子节点，再回溯计算深度；
• 迭代法本质是广度优先搜索（BFS）：按 “层” 访问节点，直接通过 “层数” 计数深度，逻辑更直观（无需回溯）；
• 选择建议：求深度时，DFS 代码更简洁，BFS 更易理解（尤其对递归不熟悉的场景）。