leetcode刷题：二叉树09（二叉树的最小深度）

111.二叉树的最小深度

力扣题目链接

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

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

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

示例:

给定二叉树 [3,9,20,null,null,15,7],

返回它的最小深度 2.

依旧使用层序遍历，当这层不满，且！！！出现了叶子节点，则出现最小深度。

package com.programmercarl.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/** * @ClassName MinDepth * @Descriotion TODO * @Author nitaotao * @Date 2022/7/3 22:32 * @Version 1.0 * 111. 二叉树的最小深度 * https://leetcode.cn/problems/minimum-depth-of-binary-tree/ **/
public class MinDepth {
    
    public int minDepth(TreeNode root) {
    
        //层序遍历，哪一行不满，即有缺省，则为最短深度
        int minDepth = 0;
        if (root == null) {
    
            return minDepth;
        }
        Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
        deque.offer(root);
        int length = 1;
        while (!deque.isEmpty()) {
    
            int size = deque.size();
            boolean flag = false;
            while (size > 0) {
    
                root = deque.poll();
                //出现叶子结点
                if (root.left == null && root.right == null) {
    
                    flag = true;
                }
                if (root.left != null) {
    
                    deque.offer(root.left);
                }
                if (root.right != null) {
    
                    deque.offer(root.right);
                }
                size--;
            }
            length *= 2;
            minDepth++;
            if (deque.size() != length && flag) {
    
                return minDepth;
            }
        }
        return minDepth;
    }
}