LeetCode_23_MinimumDepthOfBinaryTree

1. question: 二叉树的最小深度（简单）

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree

示例 1：

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

示例 2：

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

提示：

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

2. answers

这道题的思路和层序遍历一样，注意，因为遍历是一层层的，所以每次遍历时的深度是一样的，只要出现了左右孩子节点均为空，那么就是叶子节点。并且自上而下遍历，所以最先出现的叶子节点就是最小深度。

代码如下所示：

public class Solution_0021 {

    public static int minDepth(TreeNode root) {

        if(root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int length, mini = 0, depth = 0;

        all: while(!queue.isEmpty()) {

            depth ++;
            length = queue.size();

            while(length > 0) {
                root = queue.poll();

                // 叶子节点，记录其深度
                if(root.left == null && root.right == null) {
                    mini = depth;

                    break all;
                } else {

                    if(root.left != null) {
                        queue.offer(root.left);
                    }

                    if(root.right != null) {
                        queue.offer(root.right);
                    }
                }

                length --;
            }
        }

        return mini;
    }

    public static void main(String[] args) {

        TreeNode tn1 = new TreeNode(9);

        TreeNode tn2 = new TreeNode(15);
        TreeNode tn3 = new TreeNode(7);
        TreeNode tn4 = new TreeNode(20, tn2, tn3);

        TreeNode root = new TreeNode(3, tn1, tn4);

        System.out.println(minDepth(root));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。