【算法】队列与BFS

【ps】本篇有 4 道 leetcode OJ。

一、算法简介

二、相关例题

1）N 叉树的层序遍历

.1- 题目解析

.2- 代码编写

2）二叉树的锯齿形层序遍历

.1- 题目解析

.2- 代码编写

3）二叉树最大宽度

.1- 题目解析

.2- 代码编写

4）在每个树行中找最大值

.1- 题目解析

.2- 代码编写

一、算法简介

和栈类似，队列也是一种特殊的线性数据结构，是只允许在一端进行插入数据操作、在另一端进行删除数据操作的特殊线性表，具有先进先出的特性。进行插入操作（入队）的一端称为队尾，进行删除操作（出队）的一端称为队头。

队列一般与 BFS（宽度优先搜索）结合出题，而 BFS 主要的题型有树形结构相关（多为二叉树）、图论相关（最短路问题、迷宫问题、拓扑排序等）。

二、相关例题

1）N 叉树的层序遍历

429. N 叉树的层序遍历

.1- 题目解析

在对多叉树进行层序遍历的时候，是每一层从左向右依此遍历，然后再进入下一层继续从左向右依此遍历的，而遍历完一层要进入下一层时，又要回到当前层的第一个节点，通过它的孩子节点，这样才能进入下一层继续遍历，而这个过程其实是符合队列先进先出的特点的，因此队列特别适合于这类题型。

我们创建一个队列来模拟层序遍历的过程，且用一个变量来记录队列中元素的个数。若根节点不为空，就将根节点入队，此时队列中只有一个元素，仅需出队一次就能得到当前层的结果；然后将根节点的孩子节点全部入队，再记录当前队列中元素的个数，相应的，仅需出队元素的个数次就能得到当前层的结果......因此类推，直至队列中没有元素，就完成了多叉树的层序遍历。

.2- 代码编写

/*
// 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) q.push(child);}}ret.push_back(tmp); //统计最终结果}return ret;}
};

2）二叉树的锯齿形层序遍历

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

.1- 题目解析

在正常的层序遍历过程中，我们是可以把一层的节点放在一个数组中去的。既然我们有这个数组，在合适的层数逆序就可以得到锯齿形层序遍历的结果。由此，我们可以弄一个计数器 level 来记录当前的层数，当 level 为偶数时，就对数组进行逆序，再整体插入结果中。其余过程与上道题几乎相同。

.2- 代码编写

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

3）二叉树最大宽度

662. 二叉树最大宽度

.1- 题目解析

在计算二叉树的最大宽度时，还要计入空节点。

对于统计每一层的最大宽度，不难想到利用层序遍历，把当前层的结点全部存在队列里面，利用队列的长度来计算每一层的宽度，统计出最大的宽度。此外，由于空节点也是需要计算在内的，因此空节点也需要存在队列里面。但极端境况下，树的最左边一条长链，最右边也是一条长链，就需要存若干个空节点，这样就会超过最大内存限制。

不过，我们还可以想到堆，借鉴在堆中寻找根的左右孩子的方式来解题。堆的逻辑结构是一棵树，而物理结构一个顺序结构，要通过一个根节点去寻找它的左右孩子，可以根据公式 “2 * 根节点下标 + 1” 或 “2 * 根节点下标 + 2”，在顺序结构中找到左右孩子的下标。

那么，我们也可以仿照堆利用数组来存储二叉树的方式，给树节点都编上号，那么树中的空节点就可以忽略不计了，最终只需取最宽一层的最左边的节点和最右边的节点，两者的下标相减再 + 1 即可求得二叉树的最大宽度。

对一颗满二叉树进行编号，我们不难发现，如果编号是从 1 开始的，假设一个根节点的编号为 x，那么这个根节点的左孩子的编号为 2x，右孩子的编号为 2x + 1。

特别的，我们用 pair 类型将节点和其对应的编号一起存入数组中，以方便后续找到每一层的最左边节点和最右边节点。当一个节点进入数组时，只需看看它是其根节点的左孩子还是右孩子，然后根据左右孩子的编号的公式去求得它的编号即可。

但由于有效节点和空节点的个数可能很多，下标是可能溢出的，好在数据的存储是一个环形的结构，且题目说明了，数据的范围在 int 这个类型的范围之内，因此最终求下标的差值，就无需考虑溢出的情况，只需用 unsigned int 作为下标和结果的变量类型即可。

.2- 代码编写

/*** 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: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;}
};

4）在每个树行中找最大值

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

.1- 题目解析

在用队列模拟层序遍历的时候，顺便统计每一层的最大值即可。

.2- 代码编写

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