02、二叉树的最小深度

厨子大约 5 分钟数据结构算法算法基地面试递归二叉树刷题程序厨校招社招

https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/open in new window

哈喽，大家好，我是厨子，今天来说一下二叉树的最小深度这个题目

题目描述

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例 1:

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

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

最短路径是 3 → 9，深度为 2

示例 2:

输入: root = [2,null,3,null,4,null,5,null,6]
输出: 5
    2
     \
      3
       \
        4
         \
          5
           \
            6

这是一条链状结构，最小深度就是从根到叶子的距离 = 5

约束条件:

树中节点数的范围在 [0, 10^5] 内
-1000 <= Node.val <= 1000

什么是最小深度？

最小深度是从根节点到最近的叶子节点的最短路径上的节点数量，注意这里是最近的叶子节点

关键理解：

必须到达叶子节点（没有左右子节点）
从根节点开始计数
找最短的路径

        3
       / \
      9  20
        /  \
       15   7

深度计算：
- 路径 3→9: 深度 = 2 ✓（9是叶子）
- 路径 3→20: 不计入（20不是叶子）
- 路径 3→20→15: 深度 = 3 ✓（15是叶子）
- 路径 3→20→7: 深度 = 3 ✓（7是叶子）

最小深度 = min(2, 3, 3) = 2

最小深度 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: 认为只要找左右子树的最小值
        1
       /
      2
     /
    3

错误理解:
  左子树深度 = 2
  右子树深度 = 0（空）
  最小深度 = min(2, 0) = 0 ✗

正确理解:
  节点1的右子树为空，不能作为叶子路径
  必须走左子树到叶子节点3
  最小深度 = 3 ✓


误区2: 把有一个子节点的节点当作叶子
        1
       /
      2

错误: 节点2是叶子，深度 = 2 ✓
但如果节点2有子节点，就不是叶子了


误区3: 忘记根节点也算一个节点
        1

深度 = 1（不是0）

关键判断：什么时候取 min？

情况1: 左右子树都存在
        1
       / \
      2   3

min(左子树深度, 右子树深度) + 1


情况2: 只有左子树
        1
       /
      2

不能取 min(左, 0)，因为右边没有叶子，千万要注意这里的 0，不可以取 min 哦
应该走左子树: 左子树深度 + 1


情况3: 只有右子树
        1
         \
          2

不能取 min(0, 右)，因为左边没有叶子
应该走右子树: 右子树深度 + 1


情况4: 叶子节点
        1

深度 = 1

图解示例

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

        3
       / \
      9  20
        /  \
       15   7

第1步: 从叶子节点开始
━━━━━━━━━━━━━━━━━━━━━━
minDepth(9):
  左子树为空 ✓
  右子树为空 ✓
  → 9是叶子节点
  返回 1

minDepth(15):
  左子树为空 ✓
  右子树为空 ✓
  → 15是叶子节点
  返回 1

minDepth(7):
  左子树为空 ✓
  右子树为空 ✓
  → 7是叶子节点
  返回 1


第2步: 处理中间节点
━━━━━━━━━━━━━━━━━━━━━━
minDepth(20):
  左子树深度 = 1 (节点15)
  右子树深度 = 1 (节点7)
  左右子树都存在 ✓
  → 返回 min(1, 1) + 1 = 2


第3步: 处理根节点
━━━━━━━━━━━━━━━━━━━━━━
minDepth(3):
  左子树深度 = 1 (节点9，是叶子)
  右子树深度 = 2 (节点20)
  左右子树都存在 ✓
  → 返回 min(1, 2) + 1 = 2

最终结果: 2

代码实现

递归（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 minDepth(TreeNode* root) {
        // 空节点深度为0
        if (root == nullptr) {
            return 0;
        }

        // 叶子节点深度为1
        if (root->left == nullptr && root->right == nullptr) {
            return 1;
        }

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

        // 处理单边子树的情况
        // 如果左子树为空，只能走右子树
        if (root->left == nullptr) {
            return rightDepth + 1;
        }

        // 如果右子树为空，只能走左子树
        if (root->right == nullptr) {
            return leftDepth + 1;
        }

        // 左右子树都存在，取较小值
        return min(leftDepth, rightDepth) + 1;
    }
};