hot100算法刷题：二叉树的层序遍历

二叉树的层序遍历

使用队列的数据结构实现

思路：

先将根节点入队列，然后不断从队列中取出节点并访问，然后将该节点的左右孩子依次放入队列，重复过程直到队列为空

实现：

用队列q1来遍历，队列的类型为treenode*，

用二维向量v1，报错输出的结果，因为题目中的返回类型就是二维向量。

按层来存储节点的值，也就是每一层的节点值都要存储在一个 vector<int> 里，然后再把这个一维向量添加到二维向量 v1 中。可以借助一个内层循环来处理每一层的节点。

记录当前层的节点数量 int size = q1.size()；

遍历for循环，循环次数就是当前层次数size，for循环内部：

获取队首元素，返回给一个current的树节点

队首元素出队

队首元素已经保存到了current中，所以把值加入到当前层中。

判断左右孩子，如果存在，那么入队。

把每一层用1个1维的向量存储：vector currentLevel;

for循环结束，就是一层结束，把当前层加入到结果的二维向量中。即：v1.push_back( currentLevel );

下面是完整的代码：

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {// 定义队列,类型要设置为节点treenode类型queue<TreeNode*> q1;//用向量存储这个输出vector<vector<int>> v1;//树为空if(root == nullptr){return v1;}//如果queue是int，则这里要->val,  如果是treenode类型，那么current即可。q1.push(root);//遍历队列，依次出队，然后当前节点左右孩子加入队列while(!q1.empty()){int size = q1.size();vector<int> currentLevel;//遍历for循环，循环次数就是当前层次数sizefor(int i=0; i<size; i++){//取出队首节点TreeNode* current = q1.front();q1.pop();   //队首节点出队列currentLevel.push_back(current->val);   //这里必须是val，因为容器是intif(current->left){q1.push(current->left);}if(current->right){q1.push(current->right);}}v1.push_back(currentLevel);}return v1;}
};  

队列queue

queue的定义方式

方式一： 使用默认的适配器定义队列。

queue<int> q1;

方式二： 使用特定的适配器定义队列。

queue<int, vector<int>> q2;
queue<int, list<int>> q3;

注意： 如果没有为queue指定特定的底层容器，默认情况下使用deque。

queue当中常用的成员函数如下：

成员函数 功能

empty 判断队列是否为空

size 获取队列中有效元素个数

front 获取队头元素

back 获取队尾元素

push 队尾入队列

pop 队头出队列

swap 交换两个队列中的数据

示例：

#include <iostream>
#include <list>
#include <queue>
using namespace std;
int main()
{queue<int, list<int>> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << q.size() << endl; //4while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl; //1 2 3 4return 0;
}