【优选算法 | 队列 BFS】构建搜索流程的核心思维

算法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
双指针	滑动窗口	二分查找	前缀和	位运算
模拟	链表	哈希表	字符串模拟	栈模拟(非单调栈)
优先级队列

很多人学 BFS 的时候都知道“用队列”，但为什么一定是队列？它到底在整个搜索流程中起了什么作用？
其实，掌握 BFS 的关键不是死记模板，而是搞懂“层层推进、状态过渡”这个思维模式，而队列正是这个模式的天然载体。

🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏： 初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志 我自踏雪至山巅

429. N 叉树的层序遍历

【题目】：429. N 叉树的层序遍历

【算法思路】

这道题的核心是实现 ‘利用队列进行层序遍历’。每次记录队列中的元素个数，从而确定循环次数。在遍历时，我们需要使用 for (Node* child : t->children) 来访问当前节点的所有子节点，并将它们依次入队，进入下一层的遍历。

【代码实现】

/*
// 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) {//1.创建相关容器vector<vector<int>> ret;queue<Node*> q;if(root == nullptr) return ret;q.push(root);//2.进行层序变量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);}//3.返回值return ret;}
};

---

103. 二叉树的锯齿形层序遍历

【题目】：103. 二叉树的锯齿形层序遍历

【算法思路】

【代码实现】

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {//1.创建容器vector<vector<int>> ret;queue<TreeNode*> q;if(root == nullptr) return ret;q.push(root);int level = 1;//2.进行层序遍历while(q.size()){int sz = q.size();vector<int> tmp;for(int i = 0; i < sz; i++){TreeNode* 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());level++;ret.push_back(tmp);}//3.返回值return ret;}
};

---

662. 二叉树最大宽度

【题目】：662. 二叉树最大宽度

【算法思路】

解法一:硬来

虽然该解法对这道题不适用，但是可能对下一道题适用。该题如果出现，左边这种情况，啥类型范围都存储不下。

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

使用数组模拟队列时，通过 pair<TreeNode*, unsigned int> 来存储节点和编号。在每次循环中，利用 auto& [x1, y1] 拆解队列中的首尾编号，从而更新宽度。这种语法用于将复杂对象（如元组或 std::pair）解构为多个局部变量 x1 和 y1

【代码实现】

class Solution {
public:int widthOfBinaryTree(TreeNode* root) {//1.创建容器vector<pair<TreeNode*, unsigned int>> q;q.push_back({root,1});unsigned int ret = 0;//2.填表操作while(q.size()){//更新这一层的宽度(得到最后的数据)auto& [x1, y1] = q[0];auto& [x2, y2] = q.back();ret = max(ret, y2 - y1 + 1);//下一层进入队列vector<pair<TreeNode*, unsigned int>> ret;for(auto& [x, y] : q){if(x->left) ret.push_back({x->left, y*2});if(x->right) ret.push_back({x->right, y*2 + 1});}q = ret;}//3.返回值return ret;}
};

---

515. 在每个树行中找最大值

【题目】：515. 在每个树行中找最大值

【算法思路】

【代码实现】

class Solution {
public:vector<int> largestValues(TreeNode* root) {//1.创建相关容器vector<int> ret;queue<TreeNode*> q;if(root == nullptr) return ret;q.push(root);//2.进行层序变量while(q.size()){int sz = q.size();int levelMax = INT_MIN;for(int i = 0; i < sz; i++){TreeNode * t = q.front();q.pop();if(levelMax < t-> val) levelMax = t ->val;if(t-> left) q.push(t-> left);if(t-> right) q.push(t-> right);}ret.push_back(levelMax);}//3.返回值return ret;}
};

快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！