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