# 二叉树最小深度 - 层序遍历实现
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
** 说明：** 叶子节点是指没有子节点的节点。
示例 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
# 思路分析：
对于求二叉树最大深度这个规律比较好找 就是 一共有几层那么二叉树最大深度就是几，但是怎么用层序遍历去找它的最小深度呢？
结论：
层序遍历，遇到的第一个叶子节点所在层就是最小深度
我们拿 下图 二叉树来举例
其中的叶子节点分别是：4，3，7
现在我们再来领悟：遇到的第一个叶子节点所在层就是最小深度，这句话就清楚一些了，它遇到的第一个叶子节点就是最小深度
上面就是 层序遍历的结论那么结论有了些代码就容易多了。
# 代码实现：
class Solution { | |
public int minDepth(TreeNode root) { | |
if(root == null) return 0; | |
LinkedList<TreeNode> s = new LinkedList<>(); | |
s.offer(root); | |
// 记录最小深度的值 | |
int sun = 0; | |
while(! s.isEmpty()) { | |
int size = s.size(); | |
sun++; | |
for(int i = 0; i < size; i++) { | |
TreeNode poll = s.poll(); | |
// 判断如果 当前节点的 左右两边都没有 孩子了 说明 是个叶子节点那么就直接返回 最小深度值 | |
if(poll.left == null && poll.right == null) | |
return sun; | |
if(poll.left != null) | |
s.offer(poll.left); | |
if(poll.right != null) | |
s.offer(poll.right); | |
} | |
} | |
return sun; | |
} | |
} |
