104. 二叉树的最大深度

---

题目

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

示例： 示例 1:

输入: root = [3,9,20,null,null,15,7]
输出: 3

示例 2:

输入: root = [1,null,2]
输出: 2

---

解题思路

核心方法

1. 递归法：利用树的递归定义，分别计算左子树和右子树的最大深度，当前节点的深度为两者的最大值加1。
2. 迭代法：使用广度优先搜索（BFS），按层遍历树，每遍历一层深度加1，直到遍历完成。

算法步骤（递归法）

1. 终止条件：当前节点为 null 时，返回深度 0。
2. 递归左子树：计算左子树的最大深度。
3. 递归右子树：计算右子树的最大深度。
4. 计算当前深度：当前节点的深度为左右子树深度的最大值加1。

---

代码实现

递归法（Java）

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

迭代法（Java）

import java.util.*;

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
            depth++;
        }
        return depth;
    }
}

---

复杂度分析

递归法

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点会被访问一次。
• 空间复杂度：O(h)，h 是二叉树的高度。递归栈的深度取决于树的高度，最坏情况下（链状树）为 O(n)。

迭代法

• 时间复杂度：O(n)，每个节点会被入队和出队一次。
• 空间复杂度：O(m)，m 是二叉树的最大宽度，最坏情况下（完全二叉树）为 O(n)。

---

总结

1. 递归法是最直观的实现方式，代码简洁，符合树的递归结构特性。
2. 迭代法通过层序遍历避免了递归栈溢出的风险，适合处理深度较大的树。
3. 两种方法的时间效率一致，空间效率取决于树的形态，递归法受高度影响，迭代法受宽度影响。

---