Shouyu

Appearance

代码随想录 二叉树：111. 最小深度 ​

题目描述 ​

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

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

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

题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree

文章讲解：https://programmercarl.com/0111.二叉树的最小深度.html

思路 ​

深度和高度对应，那么自然，有最小深度就一定有最小高度。

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
  • 二叉树的最小深度：根节点到任意叶子节点的最短路径上的节点数量。

根节点到任意叶子节点的最短路径上的节点数量 又取决于什么？

取决于：根节点左子节点到其子树中最近叶子节点的路径上的节点数量left 和 根节点右子节点到其子树中最近叶子节点的路径上的节点数量right。这两者之间的最小值+1。

扩展一下，当前节点到任意叶子节点的最短路径上的节点数量 又取决于什么？这是我们的递归函数需要解决的问题

分情况：

  1. 当前节点是空节点，结果就是 0；
  2. 当前节点的树是单边树时，如左子节点为空，右子节点不为空时，结果就是右子节点到任意叶子节点的最短路径上的节点数量+1 ；
  3. 当前节点的左右子节点都不为空，则结果就是 左右子节点到任意叶子节点的最短路径上的节点数量的最小值+1；

一些同学可能会写如下代码：

cpp
int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);
return result;

这就是没有考虑单边子树的情况。单边子树的话，最小深度应该继承单边子树那边的最小深度

image-20250709222456542

代码实现 ​

详细注释 ​
C++
int getMinDepthFromNode(
    TreeNode
        *node) { // 获取从当前节点开始的最小深度（到最近叶子节点的节点数量）
    if (node == nullptr)
        return 0; // 空节点，路径长度为 0

    // 单层递归逻辑
    int leftPathLength =
        getMinDepthFromNode(node->left); // 左子树的最小路径长度（节点数量）
    int rightPathLength =
        getMinDepthFromNode(node->right); // 右子树的最小路径长度（节点数量）

    // 处理特殊情况：当前节点只有一个子树（即单边子树）
    // 题目定义叶子节点是左右子节点都为空的节点。
    // 如果一个节点只有一个子节点，那么它到最近叶子节点的路径必须经过那个唯一的子节点。
    if (leftPathLength == 0 && rightPathLength != 0) {
        // 左子树为空，右子树不为空，最小深度来自右子树
        return rightPathLength + 1; // 加上当前节点
    }
    if (leftPathLength != 0 && rightPathLength == 0) {
        // 右子树为空，左子树不为空，最小深度来自左子树
        return leftPathLength + 1; // 加上当前节点
    }

    // 处理常规情况：左右子树都存在，或当前节点是叶子节点（左右子树都为空）
    // 此时，选择左右子树中较短的路径，并加上当前节点自身
    int result = 1 + std::min(leftPathLength, rightPathLength);
    return result;
}

int minDepth(TreeNode *root) {
    return getMinDepthFromNode(root); // 调用辅助函数计算根节点的最小深度
}
代码简化 ​
C++
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int leftminHeight = minDepth(root->left);
        int rightminHeight = minDepth(root->right);
        if(leftminHeight == 0 && rightminHeight !=0) return rightminHeight+1;
        if(leftminHeight != 0 && rightminHeight == 0) return leftminHeight+1;
        return 1+ min(leftminHeight,rightminHeight);
    }
};

二叉树深度与高度概念一览表（包含转化关系） ​

概念归属定义测量起点测量终点特性常见算法关联深度/高度转化及关系
节点的深度 (Depth of a Node)单个节点从根节点到该节点所经过的节点数量。根节点 (计数为 1)目标节点根节点深度为 1。每向下走一层，深度加 1。前序遍历 (自顶向下)与“节点的高度”无直接通用转换公式，取决于树的结构。
节点的深度 (Height of a Node)单个节点从该节点到其最远叶子节点所经过的节点数量。目标节点最远叶子节点 (计数为 1)叶子节点高度为 1。一个节点的高度 = 其左右子树高度的最大值 + 1。后序遍历 (自底向上)与“节点的高度”无直接通用转换公式，取决于树的结构。
二叉树的最大深度 (Maximum Depth of a Binary Tree)整个二叉树从根节点到最远叶子节点所经过的节点的最大数量。根节点 (计数为 1)最远叶子节点等同于二叉树中所有叶子节点深度的最大值。递归、广度优先搜索在数值上，二叉树的最大深度 等同于 根节点的高度 (Height of Root)。
二叉树的高度 (Height of a Binary Tree)整个二叉树等同于根节点的高度，即从根节点到最远叶子节点所经过的节点的最大数量。根节点 (计数为 1)最远叶子节点等同于根节点的高度。递归 (通常用后序遍历思想)在数值上，二叉树的高度 等同于 根节点的高度 (Height of Root)。
二叉树的最小深度 (Minimum Depth of a Binary Tree)整个二叉树从根节点到最近的叶子节点所经过的节点数量。根节点 (计数为 1)最近的叶子节点 (该叶子节点左右子节点都为空)根节点到任意叶子节点的最短路径上的节点数量。注意单边子树时，需继续向下遍历到真正的叶子节点。递归、广度优先搜索 (更常用)与最大深度/高度没有直接数值上的转换关系，通常小于或等于最大深度。