刷题训练之队列与宽搜
> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。> 目标：熟练掌握字符串算法。
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
⭐知识讲解
基本思想：
- 采用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;
}
};🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
原文地址：https://blog.csdn.net/AAlykk/article/details/142455535
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！