题目
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 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
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
方法
BFS( Breath First Search )：广度优先算法
什么是广度优先算法？
BFS是一种暴力搜索算法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能地址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。
从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实现里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）
实现方法
- 首先将根节点放入队列中。
从队列中取出第一个节点，并检验它是否为目标。
- 如果找到目标，则结束搜索并回传结果。
- 否则将它所有尚未检验过的直接子节点加入队列中。
- 若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
- 重复步骤2。
来自维基百科。
大意就是利用队列先进先出的原理，需要一个队列进行遍历，存储的是同层级的数据，例如root节点加入队列，取出root节点之后需要把下一层级或者说下一步需要执行的节点加入队列，假如再加一个参数记录树的深度，就会发现好像还需要一个循环来遍历同层级的节点，以保证树深度的准确性。
解题思路
一层层遍历（树层级），同层级节点遍历，当发现了叶子节点，即没有左右子节点，就是我们结束遍历的地方，所以在遍历树层级还需要一个参数记录当前的层级。
完整代码
package org.chenly.study;
import java.util.LinkedList;
import java.util.Queue;
/**
* https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
*
* @author chenly
* @create 2020-11-14 11:41
*/
public class MinDepth111 {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public static int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
//第一个节点入队
queue.add(root);
int deep = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode treeNode = queue.poll();
TreeNode left = treeNode.left;
TreeNode right = treeNode.right;
//判断是否叶子节点
if (left == null && right == null) {
return deep;
}
if (left != null) {
queue.add(left);
}
if (right != null) {
queue.add(right);
}
}
//要在树深度层级进行层级+1
deep++;
}
return deep;
}
public static void main(String[] args) {
//TreeNode treeNode = new TreeNode(2, null, new TreeNode(3, null, new TreeNode(4, null, new TreeNode(5, null, new TreeNode(6)))));
//[3,9,20,null,null,15,7]
TreeNode treeNode = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
System.out.println(minDepth(treeNode));
}
}