队列(算法十三）

简介

几乎没有单纯之考察队列的，队列一般只作为一个辅助工具

队列常服务于BFS

queue接口

1.N叉树的层序遍历

link:

思路：

        队列 层序遍历即可

code

/*
// 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) {if(!root) return {};vector<vector<int>> ans;queue<Node*> que;que.push(root);while(!que.empty()){int sz = que.size();vector<int> tmp;while(sz--){Node* pop = que.front();tmp.push_back(pop->val);que.pop();for(auto& e:pop->children){que.push(e);}}ans.push_back(tmp);}return ans;}
};

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

link:103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

思路

        在层序遍历基础上根据deep翻转即可

code

/*** 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) {// 在层序遍历基础上来个标记为即可if(!root) return {};int deep = 0;// deep % 2 == 0 时需要逆序vector<vector<int>> ans;queue<TreeNode*> que;que.push(root);while(!que.empty()){deep++;vector<int> tmp = {};int sz = que.size();for(int i = 0; i < sz; i++){TreeNode* pop = que.front();que.pop();tmp.push_back(pop->val);if(pop->left)que.push(pop->left);if(pop->right)que.push(pop->right);}if(deep % 2 == 0)//逆序{reverse(tmp.begin(), tmp.end());}ans.push_back(tmp);}return ans;}
};

3.二叉树的最大宽度

link:662. 二叉树最大宽度 - 力扣（LeetCode）

思路：

        数组存储树 + 双端队列

        同余定理：

•         即使最后参与运算的数据很大，会int溢出
•         但是因为是减操作，只要结果不会溢出int，结果就是正确的

        unsigned 在溢出时不会报错

code1

/*** 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 模拟双端队列// 同余定理：保证即使int溢出， 结果也会正确if(!root) return 0;unsigned ans = 1;vector<pair<TreeNode*, unsigned>> dque = {{root, 1}};// unsigned 防止溢出报错while(!dque.empty()){ans = max(ans, dque.back().second - dque[0].second + 1);int sz = dque.size();for(int i = 0; i < sz; i++){pair<TreeNode*, unsigned> out = dque[0];dque.erase(dque.begin());if(out.first->left) dque.push_back({out.first->left, out.second * 2});if(out.first->right) dque.push_back({out.first->right, out.second * 2 + 1});}}return ans;}
};

code2

两个vector而不是一个队列，在层序遍历时会更方便，简洁，明了

同时使用结构化绑定

/*** 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) {if(!root) return 0;unsigned ans = 1;vector<pair<TreeNode*, unsigned>> vt = {{root, 1}};while(vt.size()){decltype(vt) tmp = {};auto& [x1, y1] = vt[0];auto& [x2, y2] = vt.back();ans = max(ans, y2 - y1 + 1);for(auto& [node, val] : vt){if(node->left) tmp.push_back({node->left, val * 2});if(node->right) tmp.push_back({node->right, val * 2 + 1});}vt.swap(tmp);}return ans;}
};

4.在每个树行中寻找最大值

link:515. 在每个树行中找最大值 - 力扣（LeetCode）

思路：

        层序遍历即可

code

两个vector代替que，简洁明了，方便易懂；

/*** 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) {if(!root) return {};vector<int> ans;vector<TreeNode*> vt = {root};while(!vt.empty()){int maxn = vt[0]->val;decltype(vt) tmp = {};for(auto& node : vt){maxn = max(maxn, node->val);if(node->left) tmp.push_back(node->left);if(node->right) tmp.push_back(node->right);}vt.swap(tmp);ans.push_back(maxn);}return ans;}
};