大三寒假要结束了，继续备战秋招，年前刷了些双指针、数组、链表的简单LeetCode题，都没有做笔记，现在也忘得差不多了，计划写一份专栏记录刷题的过程，复盘算法中的细节，由易到难，先刷简单题，再斩中等题！
一转眼就到4月份了，投递了好多暑期实习，4月份笔面试就会陆续开启，距离秋招也越来越近，这段时间在刷LeetCode Hot 100,每天刷个两道mid题，同时作个笔记，作为复盘，也作为到时笔面试前的复习资料
目录
一、关键思路：BFS（广度优先搜索）
二、BFS法优点
三、例题训练
3.1 二叉树的层序遍历
广度优先搜索（Breadth-First Search，BFS）算法是一种图形搜索算法，它从起始点开始，逐层搜索周围的节点，直到找到目标节点或者所有可达节点都被搜索到。BFS算法通常用于无权图或者所有边权相等的图中寻找最短路径。
BFS算法的基本思路是利用队列（Queue）数据结构来实现。具体实现过程如下：
BFS算法的时间复杂度为O(V+E)，其中V为节点数，E为边数。因为BFS算法需要访问所有的节点和边，所以时间复杂度是线性的。BFS算法也可以用于判断图是否为连通图，如果BFS能够访问到所有的节点，则说明图是连通图。
BFS算法的优点是找到的路径一定是最短路径，缺点是空间复杂度较高，因为需要保存所有已经访问过的节点。此外，在面对大规模的图时，BFS算法可能会陷入无限循环，因为搜索过程需要访问所有可达节点，有两大应用场景：「层序遍历」、「最短路径」
给你二叉树的根节点 root ，返回其节点值的 层序遍历 （即逐层地，从左到右访问所有节点）
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
1.创建一个队列，用于存储每一层的节点。
2.将根节点root加入队列中。
3.循环遍历队列中的节点，每次取出一个节点，并将其左右子节点加入队列中。
4.将当前节点的值存储到一个列表中，表示当前层的节点值。
5.重复步骤3和4，直到队列为空。
6.返回存储节点值的列表。
传统的BFS（广度优先搜索）算法中，遍历结果是一个一维数组，无法区分每一层，我们无法区分队列中的结点来自哪一层，而本题所需的是BFS的层序遍历版本，遍历结果应为一个二维数组，区分开每一层
因此，我们需要稍微修改一下代码，在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点。。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
vector<vector<int>>res;
if(!root)
return res;
queue <TreeNode*> q;
q.push(root);
while(!q.empty())
{
int cur =q.size();
res.push_back(vector<int>());
for(int i=0;i<cur;i++)
{
TreeNode* node = q.front();
q.pop();
res.back().push_back(node->val);
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
}
return res;
}
};