【优选算法专栏】专题十三：队列+宽搜（一）

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：算法从入门到精通
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

专题十三

N叉树的层序遍历
- 算法原理：
二叉树的锯齿形层序遍历
- 算法原理：
在每个树行中找最大值
- 算法原理：

N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）
在这里插入图片描述

算法原理：

层序遍历很简单，本题要返回一个数组，我们要在遍历的同时设置一个变量用来计数，统计队列里面有多少元素，有几个就出队几个，每出去一个就把对应的孩子弄进去
在这里插入图片描述
代码实现：

/*
// 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>> levelOrder(Node* root) {vector<vector<int>> ret;//记录最终结果queue<Node*> q;//层序遍历需要的队列if(root==nullptr)return ret;q.push(root);while(q.size()){int sz=q.size();//先求出本层需要元素的个数vector<int> tmp;//统计本层的节点for(int i=0;i<sz;i++){Node*t=q.front();q.pop();tmp.push_back(t->val);for(Node*child:t->children)//让下一层节点入队{if(child!=nullptr)q.push(child);}}ret.push_back(tmp);}return ret;}
};

二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
在这里插入图片描述

算法原理：

锯齿形类似于S型，本题是根据S型来输出结果。
在这里插入图片描述
其实本题也不难：
既然你是S型。那么我们在层序遍历的同时增加一个标记位。

当遍历到偶数层就给他逆序一下，奇数不用变即可。
代码实现：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution 
{
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret;if(root==nullptr)return ret;queue<TreeNode*>q;q.push(root);int level=1;while(q.size()){int sz=q.size();vector<int> tmp;for(int i=0;i<sz;i++){auto t=q.front();q.pop();tmp.push_back(t->val);if(t->left)  q.push(t->left);if(t->right) q.push(t->right);}//判断是否逆序？if(level %2 ==0)reverse(tmp.begin(),tmp.end());ret.push_back(tmp);level++;}return ret;}
};

在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
在这里插入图片描述

算法原理：

本题很简单，利用层序遍历，统计每一层的最大值即可。
代码实现：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution 
{
public:vector<int> largestValues(TreeNode* root) {vector<int> ret;if(root==nullptr)return ret;queue<TreeNode*>q;q.push(root);while(q.size()){int sz=q.size();int tmp=INT_MIN;for(int i=0;i<sz;i++){auto t=q.front();q.pop();tmp=max(tmp,t->val);if(t->left)q.push(t->left);if(t->right) q.push(t->right);}ret.push_back(tmp);}return ret;}
};