hot100二叉树的层序遍历
目录
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循环，循环次数就是当前层次数size
for(int i=0; i<size; i++){
//取出队首节点
TreeNode* current = q1.front();
q1.pop(); //队首节点出队列
currentLevel.push_back(current->val); //这里必须是val，因为容器是int
if(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; //4
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl; //1 2 3 4
return 0;
}