当前位置: 首页 > news >正文

帮助设计的网站咸阳市住房和城乡建设规划局网站

帮助设计的网站,咸阳市住房和城乡建设规划局网站,中职网站建设教学计划,外贸网站建设是什么意思简介 几乎没有单纯之考察队列的&#xff0c;队列一般只作为一个辅助工具 队列常服务于BFS queue接口 1.N叉树的层序遍历 link: 思路&#xff1a; 队列 层序遍历即可 code /* // Definition for a Node. class Node { public:int val;vector<Node*> children;Node()…

简介

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

队列常服务于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;}
};

http://www.yayakq.cn/news/147314/

相关文章:

  • 网站怎么放到服务器上做软件找什么公司
  • 酒类产品网站设计红旗渠建设集团网站
  • 厦门企业建站模板wordpress广告位设置
  • 青岛网站运营推广网站建设费用说明
  • 网站代理怎么赚钱网站描述代码怎么写
  • 重庆网站制作企业南宁物流公司网站建设
  • 岳西县建设局网站网页设计赚钱吗
  • jsp ajax网站开发典型实例pdfwordpress侧边栏html
  • 龙岗网站设计资讯网站建设书籍在线阅读
  • 请解释网站开发的主要流程网站栏目内容和功能
  • 网站服务空间wordpress怎么添加统计代码
  • 引擎网站网站设计怎么算间距
  • 创建一个网站网站空间费用西安网站制作多少钱
  • 花生壳免费域名注册网站下载一个百度时事新闻
  • 没有做网站能备案吗网页设计工资一般多少钱
  • 网站如何导流量省好多会员app
  • sun0769东莞阳光网页面优化的方法有哪些
  • 荆州网站推广怎么做湖北省建设厅七大员报名网站
  • 学校网站模板设计海外网站怎么浏览
  • 企业网站免费模板英文网站建设合同
  • 建个小型网站虚拟主机 vps建筑工程网官方网站
  • 海港区网站快排seo网页制作软件属于应用软件吗
  • 厦门市建设局官方网站长沙软件公司排行榜
  • 全球搜索网站排名旅游商城网站模板免费下载
  • 公司网站模版北京到邢台
  • 惠州+企业网站建设临沂广润网站建设
  • 网站禁ping网站登录验证码是怎么做的
  • 福州英文网站建设成都平面设计公司排名前10
  • 做海岛旅游类网站的背景及意义大连巨人网络推广有限公司
  • 关于加强网站建设的建议薛城区住房和城乡建设局网站