数据结构与算法学习day18-层序遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

一、层序遍历

1.题目

这道题的代码可以当做模版，解决层序遍历的类似问题

102. 二叉树的层序遍历 - 力扣（LeetCode）

2.思路

3.代码

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if(root != NULL) que.push(root);//不能操作空结点vector<vector<int>> result;while(!que.empty()){//遍历每一层int size = que.size();        //创建该层的数组vector<int> vec;for(int i = 0;i < size;i++){//取队列顶层数据TreeNode* node = que.front();//把数据删除que.pop();vec.push_back(node->val);//结束条件+把结点左右结点加进去if(node->left) que.push(node->left);if(node->right) que.push(node->right);}//把这层数据加入二维数组result.push_back(vec);}return result;}
};

二、层序遍历||

1.题目

107. 二叉树的层序遍历 II - 力扣（LeetCode）

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

2.思路

套用上面模版，读取出来的数组翻转一下即可

3.代码

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> que;if(root != NULL) que.push(root);vector<vector<int>> result;while(!que.empty()){int size = que.size();vector<int> vec;for(int i = 0;i < size;i++){TreeNode* node = que.front();que.pop();vec.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(vec);}reverse(result.begin(),result.end());return result;}
};

三、二叉树右视图

1.题目

199. 二叉树的右视图 - 力扣（LeetCode）

2.思路

这道题也可以套用第一题模版，只需要取每层数组的最后一个元素即可

3.代码

class Solution {
public:vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> que;if(root != NULL) que.push(root);//不能操作空结点vector<int> result;while(!que.empty()){//遍历每一层int size = que.size();        //创建该层的数组vector<int> vec;for(int i = 0;i < size;i++){//取队列顶层数据TreeNode* node = que.front();//把数据删除que.pop();vec.push_back(node->val);//结束条件+把结点左右结点加进去if(node->left) que.push(node->left);if(node->right) que.push(node->right);}//把这层数据尾部加入数组result.push_back(vec[size-1]);}return result;}
};

四、二叉树的层平均值

1.题目

637. 二叉树的层平均值 - 力扣（LeetCode）

2.思路

加入每层平均即可

3.代码

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> que;vector<double> result;if(root != NULL) que.push(root);while(!que.empty()){int size = que.size();double temp = 0;for(int i = 0;i<size;i++){TreeNode* node = que.front();que.pop();temp+=node->val;if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(temp/size);}return result; }
};

五、N叉树的层序遍历

1.题目

429. N 叉树的层序遍历 - 力扣（LeetCode）

2.思路

用这个方法遍历其他儿子

3.代码

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {queue<Node*> que;if(root != NULL) que.push(root);//不能操作空结点vector<vector<int>> result;while(!que.empty()){//遍历每一层int size = que.size();        //创建该层的数组vector<int> vec;for(int i = 0;i < size;i++){//取队列顶层数据Node* node = que.front();//把数据删除que.pop();vec.push_back(node->val);for(Node* child:node->children){que.push(child);}}//把这层数据加入二维数组//result.push_back(move(vec));result.push_back(vec);}return result;       }
};

六、在每个树行中找最大值

1.题目

515. 在每个树行中找最大值 - 力扣（LeetCode）

2.思路

在每层的数组找出最大值即可

3.代码

class Solution {
public:int getMax(vector<int> vec){int size = vec.size();int temp = vec[0];if(size>1){for(int i=1;i<size;i++){if(vec[i]>temp) temp = vec[i];}}return temp;}vector<int> largestValues(TreeNode* root) {queue<TreeNode*> que;if(root != NULL) que.push(root);//不能操作空结点vector<int> result;while(!que.empty()){//遍历每一层int size = que.size();        //创建该层的数组vector<int> vec;for(int i = 0;i < size;i++){//取队列顶层数据TreeNode* node = que.front();//把数据删除que.pop();vec.push_back(node->val);//结束条件+把结点左右结点加进去if(node->left) que.push(node->left);if(node->right) que.push(node->right);}//把这层数据加入二维数组result.push_back(getMax(vec));}return result;       }
};