111. 二叉树的最小深度（BFS）

小灰灰 2023-10-05 14:54 13阅读 0赞

#### 111. 二叉树的最小深度 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

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

说明：叶子节点是指没有子节点的节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
**提示：**

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

## 解题思路 ##

这题一看要求最短路径，第一反应就是BFS。 这题很简单直接套用BFS模板就行了。

## 代码 ##

class Solution {
        
            public int minDepth(TreeNode root) {
        
            Queue<TreeNode> queue=new LinkedList<>();//核心数据结构
            if(root==null){
        
                return 0;
            }
            queue.add(root);//首先把根节点给加到队列中
            int step=0;//初始化步数为0
    
            while(!queue.isEmpty()){
        //当队列不空的时候
                step++;//首先步数加一，之所以写在最前面，是因为把root放入队列这也算一步
                int size=queue.size();
                /* 将当前队列中的所有节点向四周扩散 */
                while(size-->0){
        
                    TreeNode tree=queue.poll();
                    if(tree.left==null&&tree.right==null){
        //满足目标直接返回
                        return step;
                    }
    
                    if(tree.left!=null){
        //如果它有节点就把节点放入队列
                        queue.add(tree.left);
                    }
                    if(tree.right!=null){
        
                        queue.add(tree.right);
                    }
                }
            }
            return -1;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201202235149713.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70