11、二叉树的最大深度

哈喽，大家好，今天来给大家写一下，二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

完成这个题目之后，二叉树的最小深度也不在话下了

题目描述

给定一个二叉树，找出其最大深度。

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

说明: 叶子节点是指没有子节点的节点。

示例 1:

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

从根节点3到叶子节点9的路径: 3 → 9（深度2）
从根节点3到叶子节点15的路径: 3 → 20 → 15（深度3）
从根节点3到叶子节点7的路径: 3 → 20 → 7（深度3）

最长路径是 3 → 20 → 15 或 3 → 20 → 7，深度为 3

示例 2:

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

最长路径是 1 → 2，深度为 2

约束条件:

• 树中节点的数量在 [0, 10^4] 范围内
• -100 <= Node.val <= 100

什么是最大深度？

最大深度的定义

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

关键理解：

1. 从根节点开始计数
2. 到达叶子节点没有左右子节点）
3. 找最长的路径

        3
       / \
      9  20
        /  \
       15   7

深度计算：
- 路径 3→9: 深度 = 2
- 路径 3→20→15: 深度 = 3
- 路径 3→20→7: 深度 = 3

最大深度 = max(2, 3, 3) = 3

最大深度 vs 最小深度

        1
       / \
      2   3
     /
    4

最大深度（到最远的叶子）:
- 路径 1→2→4: 深度 = 3
- 路径 1→3: 深度 = 2
最大深度 = max(3, 2) = 3

最小深度（到最近的叶子）:
- 路径 1→3: 深度 = 2（3是叶子）
- 路径 1→2→4: 深度 = 3（4是叶子）
- 注意：1→2 不算（2不是叶子）
最小深度 = min(2, 3) = 2

解题思路

核心思想

找到最远的叶子节点，计算从根到该叶子的路径长度。

关键点：

1. 空节点深度为 0
2. 叶子节点深度为 1
3. 非叶子节点深度 = max(左子树深度, 右子树深度) + 1

算法流程

暂时无法在飞书文档外展示此内容

图解示例

以示例1为例：[3,9,20,null,null,15,7]

        3
       / \
      9  20
        /  \
       15   7

第1步: 从叶子节点开始（自底向上）
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
maxDepth(9):
  左子树为空 → 深度0
  右子树为空 → 深度0
  返回 max(0, 0) + 1 = 1

maxDepth(15):
  左子树为空 → 深度0
  右子树为空 → 深度0
  返回 max(0, 0) + 1 = 1

maxDepth(7):
  左子树为空 → 深度0
  右子树为空 → 深度0
  返回 max(0, 0) + 1 = 1


第2步: 处理中间节点
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
maxDepth(20):
  左子树深度 = 1 (节点15)
  右子树深度 = 1 (节点7)
  返回 max(1, 1) + 1 = 2


第3步: 处理根节点
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
maxDepth(3):
  左子树深度 = 1 (节点9)
  右子树深度 = 2 (节点20)
  返回 max(1, 2) + 1 = 3

最终结果: 3

单边子树的处理

示例: [1,2]

    1
   /
  2

处理过程:
  leftDepth = maxDepth(2) = 1
  rightDepth = maxDepth(null) = 0
  return max(1, 0) + 1 = 2 ✓

与最小深度对比:
最小深度需要特殊处理单边子树（不能直接取min）
最大深度不需要特殊处理（直接取max即可）

代码实现

递归（DFS）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        // 递归终止条件：空节点深度为0
        if (root == nullptr) {
            return 0;
        }

        // 递归计算左右子树的最大深度
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        // 返回左右子树最大深度的较大值 + 1
        return max(leftDepth, rightDepth) + 1;
    }
};

时间复杂度: O(n)，n 是节点总数，每个节点访问一次

空间复杂度: O(h)，h 是树的高度（递归栈深度）

• 最坏情况（链状树）：O(n)
• 最好情况（平衡树）：O(log n)