【BFS】111. Minimum Depth of Binary Tree

问题：

求给定二叉树的最短深度。

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints:
The number of nodes in the tree is in the range [0, 105].
-1000 <= Node.val <= 1000

解法：BFS（广度优先搜索 Breadth-First-Search）

框架：

 1 // 计算从起点 start 到终点 target 的最近距离
 2 int BFS(Node start, Node target) {
 3     queue<Node> q; // 核心数据结构
 4     unordered_set<Node> visited; // 避免走回头路
 5 
 6     q.push(start); // 将起点加入队列
 7     visited.insert(start);
 8     int step = 0; // 记录扩散的步数
 9 
10     while (!q.empty()) {
11         int sz = q.size();
12         /* 将当前队列中的所有节点（同一层节点）向四周扩散 */
13         for (int i = 0; i < sz; i++) {
14             Node cur = q.front();
15             q.pop();
16             /* 划重点：这里判断是否到达终点 */
17             if (cur == target)
18                 return step;
19             /* 将 cur 的相邻节点加入队列 */
20             for (Node x : cur.next())
21                 if (visited.count(x)==0) {
22                     q.push(x);
23                     visited.insert(x);
24                 }
25         }
26         /* ★划重点：更新步数在这里（下一层节点） */
27         step++;
28     }
29 }

比较	DFS	BFS
名称	深度优先搜索（Depth-First-Search）	广度优先搜索（Breadth-First-Search）
数据结构	STACK 栈	QUEUE 队列
形象	单线	面
说明	单路尝试->回退->再尝试...	多路齐头并进
解决问题	回溯问题	图的始末节点最短路径问题

对于本问题，

到达终点：左右子节点=null
将当前节点的所有相邻节点加入queue，作为下一层待探索节点：所有相邻节点->左右子节点
树：非图的特殊性，不存在重复访问相邻节点的可能性，去掉visited

代码参考：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     int minDepth(TreeNode* root) {
15         int res = 1;
16         queue<TreeNode*> q;
17         //unordered_set<TreeNode*> visited;
18         if(root==nullptr) return 0;
19         q.push(root);
20         //visited.insert(root);
21         
22         while(!q.empty()) {
23             int sz = q.size();
24             for(int i = 0; i < sz; i++) {
25                 TreeNode* cur = q.front();
26                 q.pop();
27                 if(cur->left==nullptr && cur->right==nullptr) return res;
28                 if(cur->left) { //&& visited.count(cur->left) == 0) {
29                     q.push(cur->left);
30                     //visited.insert(cur->left);
31                 }
32                 if(cur->right) {// && visited.count(cur->right) == 0) {
33                    ` q.push(cur->right);
34                     //visited.insert(cur->right);
35                 }
36                 
37             }
38             res++;
39         }
40         return res;
41     }
42 };