队列+二叉树广度优先

题目出自力扣-n叉树的层序遍历
在这里插入图片描述

我是原始人，递归写出一道题就只有递归思路，开始的想法是写深搜函数，传一个随着层数递增的int参数q，节点空就return，否则遍历所有节点，每个子节点又以q+1为层数递归，然后收集每一层的val即可
代码;

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:
vector<vector<int>>s;
//int q=0;
void d(Node*root,int q){if(root==nullptr)return ;if(s.size()<=q)s.resize(q+1);s[q].push_back(root->val);for(int i=0;i<root->children.size();i++){d(root->children[i],q+1);}//return ;
}vector<vector<int>> levelOrder(Node* root) {d(root,0);return s;}
};

很经典的递归，
看了官方题解后豁然开朗，原来队列这么好玩
广度优先搜索：
对于「层序遍历」的题目，我们一般使用广度优先搜索。在广度优先搜索的每一轮中，我们会遍历同一层的所有节点。
具体地，我们首先把根节点 root 放入队列中，随后在广度优先搜索的每一轮中，我们首先记录下当前队列中包含的节点个数（记为 cnt），即表示上一层的节点个数。在这之后，我们从队列中依次取出节点，直到取出了上一层的全部 cnt 个节点为止。当取出节点 cur 时，我们将 cur 的值放入一个临时列表，再将 cur 的所有子节点全部放入队列中。
当这一轮遍历完成后，临时列表中就存放了当前层所有节点的值。这样一来，当整个广度优先搜索完成后，我们就可以得到层序遍历的结果。
知道你不想看文字，先上代码，我们跟代码走

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {if (!root) {return {};}                          //特判就给个空树的情况vector<vector<int>> ans;  //存放大容器，就是你要返回的答案queue<Node*> q;           //主角q.push(root);             //第一层就这哥们一个，直接进来while (!q.empty()) {        //不必纠结，队列在此期间进进出出，全遍历收集完才会break出来，往下看int cnt = q.size();         //记录当前队列长度，它把控了当前层的长度 vector<int> level;                 //是ans大容器的子集，用来存储每层数据  for (int i = 0; i < cnt; ++i) {   //不是遍历队列！！！，不要这么理解，是遍历当前层的节点，数量严格是当前层节点数，这样就保证Node* cur = q.front();         //这样就保证了level分层装q.pop();                        //但当前层，从队列中慢慢抽出，来一个pop一个，level.push_back(cur->val);      //记录进levelfor (Node* child: cur->children) {    q.push(child);            //迭代器把下一层的节点推进队列，不影响上面的遍历，应=因为上一轮的cnt已经定好}}ans.push_back(move(level));     //一层层打包进ans;}return ans;     //艺术已成}
};