📃 题目描述

题目链接：111. 二叉树的最小深度 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

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

🔔 解题思路

递归法

和求最大深度一样，不过有一点需要注意，举个例子：

    3
     \
     20
    /  \
   15   7
         \
       	  11

这颗二叉树的最小深度是 3，而不是 1。因为题目中指明了，最小深度是从根节点到最近叶子节点的最短路径上的节点数量，一定要走到叶子节点才行。

如果我们还用求最大深度的那段代码：

// 左子树的高度
int leftDepth = maxDepth(root.left);
// 右子树的高度
int rightDepth = maxDepth(root.right);

return Math.min(leftDepth, rightDepth) + 1;

如果这样写的话，没有左孩子的分支显然就会被算作最短深度。

可能有同学会问，求最大深度里也写明了一定要走到叶子节点才行，为什么这段代码就行呢？

太显然了，求最大深度一定会走到叶子节点呀，题目写不写都是一样的，因为如果某个节点他有叶子节点，那求最大深度的时候一定会走到那，对吧；

但是如果求最小深度的话，走到叶子节点反而会增加深度，所以为了防止我们不走到叶子节点，题目才特此写明。

所以，对于求最小深度中的左右子树，我们需要作额外的处理：

• 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度
• 反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度
• 最后如果左右子树都不为空，返回左右子树深度最小值 + 1

具体代码如下：

class Solution {
    public int minDepth(TreeNode root) {    
        // 递归出口
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }

        // 左子树的高度
        int leftDepth = minDepth(root.left);
        // 右子树的高度
        int rightDepth = minDepth(root.right);

        // 左子树为空，右子树不为空
        if (leftDepth == 0) {
            return rightDepth + 1;
        }
        // 右子树为空，左子树不为空
        else if (rightDepth == 0) {
            return leftDepth + 1;
        }
        // 左右子树都不为空
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

迭代法

同样的，需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

class Solution {
    public int minDepth(TreeNode root) {    
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root);

        int depth = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            depth ++;

            for (int i = 0; i < size; i ++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }

                // 只有当左右孩子都为空的时候，才说明遍历的最低点了
                if (cur.left == null && cur.right == null) {
                    return depth;
                }
            }
        }

        return depth;
    }
}

💥 复杂度分析

• 空间复杂度：O(LogN)
• 时间复杂度：O(N)