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