队列+宽搜_429. N 叉树的层序遍历_二叉树最大宽度
429. N 叉树的层序遍历

定义一个队列q,将一层的节点入队,并记录节点个数。根据节点的个数,出队列,并将其孩子入队列。出完队列,队列当前剩余节点的个数就是下次出队列的次数。直到队列为空
/*
// 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>> re;queue<Node*> q;if(root==nullptr) return re;q.push(root);while(!q.empty()){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) //入队当前节点孩子vector<Node*> children{if(child!=nullptr) q.push(child);}}re.push_back(tmp);}return re;}
};
662. 二叉树最大宽度


我们知道二叉树可以用用数组表示,定义根节点下标为1,它左孩子下标就是2,右孩子3.
所以 父母节点节点下标 i ,左孩子下标i*2 右孩子下标i*2+1。
1.存入队列中的元素类型为pair<TreeNode*,int>,也要把对应节点的下标传过去。
2.知道队列头节点的下标 尾节点的下标 : i尾 - i头 +1 尾两节点的距离就是当前层最长的距离
3.算完当前层,再把它们左右孩子入队列,直到队列为空.
/*** 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) {uint32_t re=0;vector<pair<TreeNode*,uint32_t>> q;q.push_back(make_pair(root,1));while(q.size()){//1.记录当前层的最大宽度auto&[x1,y1]=q[0];auto&[x2,y2]=q.back();uint32_t tmp=y2-y1+1;re=max(re,tmp);//2.更新q队列的节点(换下一层)vector<pair<TreeNode*,uint32_t>> t;for(auto&[x,y]:q){if(x->left) t.push_back({x->left,y*2});if(x->right) t.push_back({x->right,y*2+1});}q=t;}return re;}
};
用数组模拟队列,便于找头尾节点。
出队父母节点,入队其孩子节点。不在原数组q上进行,另开数组t入队其孩子节点。入完后再把存有孩子节点的数组t复制到原数组q上,减少数组出队列移动元素的时间。
515. 在每个树行中找最大值

遍历每一层,把每一次的最大值找出来
/*** 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> re;if(root==nullptr) return re;queue<TreeNode*> q;q.push(root);while(!q.empty()){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);}re.push_back(tmp);}return re;}
};
相关文章:
队列+宽搜_429. N 叉树的层序遍历_二叉树最大宽度
429. N 叉树的层序遍历 定义一个队列q,将一层的节点入队,并记录节点个数。根据节点的个数,出队列,并将其孩子入队列。出完队列,队列当前剩余节点的个数就是下次出队列的次数。直到队列为空 /* // Definition for a Nod…...
Windows11安装及使用nvm
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 Windows11安装nvm 前言一、简介二、下载三、安装1、双击运行,同意协议,点击Next2、选择nvm安装路径,此路径也是环境变量NVM_HOME的路径&am…...
(一)机器学习 - 入门
数据集 数据集是一组数据的集合,这些数据可以是数值型、文本型、图形型等多种形式。数据集通常用于统计分析、机器学习、科学研究、商业智能等领域,以发现数据中的模式、趋势和关联性。 数据集的组成: 变量(Variables)…...
【解决】k8s使用kubeadm初始化集群失败问题整理
执行提示命令,查看报错信息 journalctl -xeu kubelet1、错误:running with swap on is no 报错 "command failed" err"failed to run Kubelet: running with swap on is no 解决: swap未禁用,需要禁用swap&…...
apache-dubbo
dubbo 文档地址 dubbo 官方文档地址 https://dubbo.apache.org/zh-cn/docs/user/references/api.html nacos 官方文档地址 https://nacos.io/zh-cn/docs/quick-start.html nacos下载地址 https://github.com/alibaba/nacos/releases/download/2.3.0/nacos-server-2.3.0.…...
ECharts柱状图-柱图2,附视频讲解与代码下载
引言: 在数据可视化的世界里,ECharts凭借其丰富的图表类型和强大的配置能力,成为了众多开发者的首选。今天,我将带大家一起实现一个柱状图图表,通过该图表我们可以直观地展示和分析数据。此外,我还将提供…...
【新人系列】Python 入门(十六):正则表达式
✍ 个人博客:https://blog.csdn.net/Newin2020?typeblog 📝 专栏地址:https://blog.csdn.net/newin2020/category_12801353.html 📣 专栏定位:为 0 基础刚入门 Python 的小伙伴提供详细的讲解,也欢迎大佬们…...
HTML综合
一.HTML的初始结构 <!DOCTYPE html> <html lang"en"><head><!-- 设置文本字符 --><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><!-- 设置网页…...
孚盟云 MailAjax.ashx SQL注入漏洞复现
0x01 产品简介 上海孚盟软件有限公司是一家外贸SaaS服务提供商,也是专业的外贸行业解决方案专业提供商。 全新的孚盟云产品,让用户可以用云模式实现信息化管理,让用户的异地办公更加流畅,大大降低中小企业在信息化上成本,用最小的投入享受大型企业级别的信息化服务,主要…...
解决“VMware虚拟机报Intel VT-x”错误
今天,在windows系统上,打开VMware WorkStation v15软件里的虚拟机,弹出"Intel VT-x处于禁用状态"错误,如图(1)所示: 图(1) 虚拟机报"Intel VT-x"错误 问题原因:当前电脑的BIOS没有开启…...
NiceGUI `ui.table` 基础
NiceGUI ui.table 基础 ui.table 是 NiceGUI 提供的一个组件,用于在页面上展示数据表格 基本概念 官方简介 A table based on Quasar’s QTable component. 参数参考rows:list of row objects; 行对象列表columns:list of column objects (defaults to the colu…...
分布式 Raft算法 总结
前言 相关系列 《分布式 & 目录》《分布式 & Raft算法 & 总结》《分布式 & Raft算法 & 问题》 参考文献 《Raft一致性算法论文译文》《深入剖析共识性算法 Raft》 简介 Raft 木筏是一种基于日志复制实现的分布式容错&一致性算法。在Raft算法…...
C++ 中面向对象编程如何实现动态绑定?
在 C 中,动态绑定(Dynamic Binding)是通过 虚函数(virtual function) 和 多态性(polymorphism) 来实现的。这是面向对象编程的重要特性之一,它允许程序在运行时根据对象的实际类型调…...
微服务-01
1.认识微服务 1.1 单体架构 单体架构(monolithic structure):顾名思义,整个项目中所有功能模块都在一个工程中开发;项目部署时需要对所有模块一起编译、打包;项目的架构设计、开发模式都非常简单。 当项目…...
这是一个vue3 + scss的数字滚动效果
介绍: 当数字变化时,只改变变化的数字位,其余的不变,可以递增、递减、骤变、负数也可以,但是样式要根据具体的项目需求去改; 效果1、增加数字: 效果2、减少数字: 使用方法: <te…...
数字证书管理工具 openssl keytool
OPENSSL 命令 openssl command [ command_opts ] [ command_args ] 常用command: version 用于查看版本信息 enc 用于加解密 ciphers 列出加密套件 genrsa 用于生成私钥 -des|-des3|-idea:用来加密私钥文件的三种对称加密算法。 rsa …...
Polars数据聚合与旋转实战教程
在这篇博文中,我们的目标是解决数据爱好者提出的一个常见问题:如何有效地从Polars DataFrame中创建汇总视图,以便在不同时间段或类别之间轻松进行比较。我们将使用一个实际的数据集示例来探索实现这一目标的各种方法。 Polars简介 Polars 是…...
引用类型集合的深拷贝,无需手动写循环:Apache Commons Lang (SerializationUtils)
在java中,我们如果想要对引用类型的集合进行深拷贝。有一种方式,就是调用SerializationUtils Apache Commons Lang (SerializationUtils) Apache Commons Lang 提供了 SerializationUtils 类,可以利用 Java 的序列化机制来进行集合及其元素…...
HTML、CSS表格的斜表头样式设置title 画对角线
我里面有用到layui框架的影响,实际根据你自己的框架来小调下就可以 效果如下 上代码 <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-wi…...
docker 安装mysql 5.7 详细保姆级教程
1. 安装mysql(5.7) docker pull mysql:5.7 若是拉取不了,可以配置下 docker 源 2. 查看是否安装成功 docker images 下图就是成功了 3.创建mysql专用目录、数据挂载目录、配置文件目录 ,演示目录在于/home/下 //命令逐条执行cd /home/ mkdir mysql …...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...
