【宽搜】1. 层序遍历模板讲解

题目描述

题目链接：N叉树的层序遍历

层序遍历流程

请仔细阅读下图：

根据上图的流程，下面再明确几个问题：
1. 为什么要使用队列？

队列是先进先出的数据结构，在数的层序遍历中，需要先将节点push进来，最终将节点先pop出去，这符合队列的特性

2. 如何控制将每一层的元素push进队列并最终加入到vector中？

将A节点pop出队列的时候就将A的孩子push进队列。这样当A节点这一层都pop出队列的时候A节点的下一层就全部进入到队列中了。队列的size就是这一层的节点个数。当遍历完size时，就说明这一层都遍历完了，此时就可以将已经装好这一层元素的vector push_back()进vector<vector< int >>中了。

代码

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> res;queue<Node*> q;if (root == nullptr){return res;}q.push(root);while(q.size()){//这两个值在这里定义是因为每一层都需要重新定义，会变化vector<int> tmp;int sz = q.size();   //记录q的size，其实就是数的每一层的节点个数//这里是对数的每一层进行操作了for (int i = 0; i < sz; ++ i){Node* t = q.front();//将t从队列中pop出去q.pop();//同时将这一层的元素一个一个都push_back()进vector中tmp.push_back(t->val);//t的孩子都push进队列中 --> 因为push和pop都会影响到队列的size//如果前面不将当时的size保存到sz中，会出现混乱的问题for (Node* child : t->children){   if (child != nullptr)q.push(child);}}//走到这里，说明数的一层遍历完了//将这一层的节点的值push_back()到vector<cevtor<int>>中res.push_back(tmp);}return res;}
};

这个代码就是层序遍历的模板，层序遍历就用这个模板就行了。然后根据不同的题目进行简单的改变。