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

111. 二叉树的最小深度

• 题目
• 解题思路
• 代码

题目

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

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

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

提示：

• 树中节点数的范围在 [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;
    }
}