🔗 二叉树的最大深度

题目来源：104. 二叉树的最大深度 – 力扣（LeetCode）

📌 题目描述

给定一个二叉树 root，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

✅ 示例解析

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3
解释：从根节点 3 出发，最长路径为 3 → 20 → 15（或 7），共 3 个节点。

示例 2：

输入：root = [1,null,2]
输出：2
解释：路径为 1 → 2，共 2 个节点。

示例 3：

输入：root = []
输出：0
解释：空树没有节点，深度为 0。

⚠️ 提示

• 树中节点的数量在 [0, 10⁴] 区间内。
• -100 <= Node.val <= 100

💡 解法：深度优先搜索（DFS）递归 —— O(n) 时间，O(h) 空间

class Solution {
    public int maxDepth(TreeNode root) {
        return dfs(root);
    }

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

📊 复杂度分析

• 时间复杂度：O(n)
  每个节点恰好被访问一次，总共有 n 个节点，因此时间复杂度为 O(n)。
• 空间复杂度：O(h)
  递归调用栈的深度等于树的高度 h。最坏情况下（树退化为链表），h = n；最好情况下（完全平衡树），h = log n。因此空间复杂度为 O(h)。

🧩 解题思路

递归思想：
一棵二叉树的最大深度 = 1（当前根节点） + 左右子树中深度较大的那个。

核心逻辑：

• 如果当前节点为空，返回深度 0。
• 否则，分别递归计算左子树和右子树的深度。
• 取两者最大值加 1，即为当前树的深度。