刷题训练之队列与宽搜

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：熟练掌握字符串算法。

> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。

> 专栏选自：刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言分析

最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

⭐知识讲解

基本思想：

采用BFS算法
采用模拟细想

🌙topic-->1

题目链接：1. - 力扣（LeetCode）

题目分析：

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

算法原理：

解法：BFS

图解：

代码演示：

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;}
};

🌙topic-->2

题目链接：2. - 力扣（LeetCode）

题目分析：

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

算法原理：

解法：层序遍历

图解：

代码演示：

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;}
};

🌙topic-->3

题目链接：3. - 力扣（LeetCode）

题目分析：

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。（树的 最大宽度 是所有层中最大的宽度）

算法原理：

解法：利用数组存储二叉树的方式，给结点编号

图解：

代码演示：

class Solution {
public:int widthOfBinaryTree(TreeNode* root) {vector<pair<TreeNode*, unsigned int>> q; // ⽤数组模拟队列q.push_back({root, 1});unsigned int ret = 0;while (q.size()) {// 先更新这⼀层的宽度auto& [x1, y1] = q[0];auto& [x2, y2] = q.back();ret = max(ret, y2 - y1 + 1);// 让下⼀层进队vector<pair<TreeNode*, unsigned int>> tmp; // 让下⼀层进⼊这个队列for (auto& [x, y] : q) {if (x->left)tmp.push_back({x->left, y * 2});if (x->right)tmp.push_back({x->right, y * 2 + 1});}q = tmp;}return ret;}
};

🌙topic-->4

题目链接：4. - 力扣（LeetCode）

题目分析：

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

算法原理：

解法：利用层序遍历，统计出每一层的最大值

图解：

这个题目和上面的极其相似，所以就不再讲解了

代码演示：

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;}
};