邯郸单位网站建设,域名注册后怎么使用,男科医院网站建设公司,合肥公司网站建设价格简介
几乎没有单纯之考察队列的#xff0c;队列一般只作为一个辅助工具
队列常服务于BFS queue接口 1.N叉树的层序遍历
link:
思路#xff1a; 队列 层序遍历即可
code
/*
// Definition for a Node.
class Node {
public:int val;vectorNode* children;Node()…简介
几乎没有单纯之考察队列的队列一般只作为一个辅助工具
队列常服务于BFS queue接口 1.N叉树的层序遍历
link:
思路 队列 层序遍历即可
code
/*
// Definition for a Node.
class Node {
public:int val;vectorNode* children;Node() {}Node(int _val) {val _val;}Node(int _val, vectorNode* _children) {val _val;children _children;}
};
*/class Solution {
public:vectorvectorint levelOrder(Node* root) {if(!root) return {};vectorvectorint ans;queueNode* que;que.push(root);while(!que.empty()){int sz que.size();vectorint 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:vectorvectorint zigzagLevelOrder(TreeNode* root) {// 在层序遍历基础上来个标记为即可if(!root) return {};int deep 0;// deep % 2 0 时需要逆序vectorvectorint ans;queueTreeNode* que;que.push(root);while(!que.empty()){deep;vectorint 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;vectorpairTreeNode*, 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){pairTreeNode*, 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;vectorpairTreeNode*, 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:vectorint largestValues(TreeNode* root) {if(!root) return {};vectorint ans;vectorTreeNode* 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;}
};
