LeetCode 111. 二叉树的最小深度

2025-12-18 HGNULB 约 4 分钟

文章信息 15 个分类 6 个标签

分类

LeetCode CodeTop 简单已解决已掌握 20-50 字节跳动美团阿里巴巴快手腾讯猿辅导华为小米哔哩哔哩

题目描述

✅ 111. 二叉树的最小深度

题意分析

题目要的是从根节点到最近叶子节点这条路径上的节点个数。两个词都必须抠死：路径的终点只能是叶子，而叶子的定义是「左右孩子都为空」的节点；长度按节点数计，不是边数，所以只有根节点的树答案是 1，空树答案是 0。

最容易被忽略的信号是「只有一个孩子的节点不是叶子」。一个节点若左孩子为空、右孩子存在，它自己并没有到达终点，那条空掉的左边根本不是一条可以走完的路径，而是「此路不通」。反过来说，缺失的一侧不提供任何候选答案，只有真正能走到叶子的那一侧才算数。这正是本题与「二叉树的最大深度」的分水岭：求最大深度时，空子树贡献 0 不会影响取最大值，天然被忽略；求最小深度时，空子树贡献的 0 会被当成「零步就到终点」而抢走最小值，必须显式排除。

边界还包括：树可能退化成一条链，此时唯一的叶子在链尾，答案等于节点总数；节点值不影响答案，只有结构相关。

解法：DFS 区分单子树边界

核心思路

定义 minDepth(node) 为从 node 到其子树中最近叶子节点的节点数，空树返回 0。关键是空孩子表示“没有路径”，不能拿这个 0 与真实子树深度取最小值。

因此要按孩子是否存在分情况：若左子树为空，只能走右子树；若右子树为空，只能走左子树；两侧都存在时才取较小深度。叶子两侧都空，会在第一个单侧分支中得到 minDepth(null)+1=1。

递归始终保证返回值对应一条真正到达叶子的路径。假设左右子树返回值正确，单侧节点只能选择存在的一侧，两侧节点选择较短的一侧，最后加上当前节点，所以按树高归纳可知结果正确。

解题步骤

根节点为空时返回 0。

左孩子为空时返回 minDepth(root.right)+1；叶子节点也包含在此情况中。

右孩子为空时返回 minDepth(root.left)+1。

左右孩子都存在时，返回两侧最小深度加 1。

对左斜链 [1,2,null,3]，每层都只能沿左子树继续，返回值从叶子的 1 逐层加到 3。若直接写 1+min(left,right)，空的右子树会以 0 被选中，错误得到 1。

代码实现

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null) {
            // 只有右子树时，最近叶子只能在右子树中。
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left == nil {
        // 空子树不能作为叶子路径参与最小值比较。
        return minDepth(root.Right) + 1
    }
    if root.Right == nil {
        return minDepth(root.Left) + 1
    }
    left := minDepth(root.Left)
    right := minDepth(root.Right)
    if left < right {
        return left + 1
    }
    return right + 1
}

复杂度分析

时间复杂度：$O(n)$，每个节点访问一次。

空间复杂度：$O(h)$，h 为树高，对应递归栈；退化链表时为 $O(n)$。

关键点总结

最小深度的终点必须是叶子；只有一个孩子的节点不能作为终点。

空子树返回 0 表示路径不存在，不能参与 min 比较。

两侧都存在才取最小值，单侧存在只能沿该侧递归。

面试口述时先指出它与最大深度模板的差别，再写三个结构分支，最能体现边界意识。

易错点总结

直接写 1+min(left,right)：[1,2] 会把空右子树的 0 当成最短路径，错误返回 1。

用 left==null || right==null 判断叶子：单孩子节点会被提前当成叶子；叶子要求两侧都为空。

空树返回 1：空树答案应为 0，单节点树才是 1。

把深度按边数计算：题目统计节点数，[1] 的答案是 1。

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	取 max 时空子树天然被忽略，无需单侧特判，与本题正相反
110. 平衡二叉树	简单	求高度的同时向上传递不平衡信号，考察递归的剪枝返回
559. N 叉树的最大深度	简单	孩子数不定，需遍历 children 列表而非固定左右两支
剑指 Offer 55 - I. 二叉树的深度	简单	最大深度的等价题，可用来对照两种取极值方向的写法差异
剑指 Offer 55 - II. 平衡二叉树	简单	用 `-1` 作为哨兵返回值提前终止，练习返回值语义的设计
面试题 04.04. 检查平衡性	简单	同一判定的另一版本，适合练习自底向上一次遍历的写法