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

队列+宽搜_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&#xff0c;将一层的节点入队&#xff0c;并记录节点个数。根据节点的个数&#xff0c;出队列&#xff0c;并将其孩子入队列。出完队列&#xff0c;队列当前剩余节点的个数就是下次出队列的次数。直到队列为空 /* // Definition for a Nod…...

Windows11安装及使用nvm

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 Windows11安装nvm 前言一、简介二、下载三、安装1、双击运行&#xff0c;同意协议&#xff0c;点击Next2、选择nvm安装路径&#xff0c;此路径也是环境变量NVM_HOME的路径&am…...

(一)机器学习 - 入门

数据集 数据集是一组数据的集合&#xff0c;这些数据可以是数值型、文本型、图形型等多种形式。数据集通常用于统计分析、机器学习、科学研究、商业智能等领域&#xff0c;以发现数据中的模式、趋势和关联性。 数据集的组成&#xff1a; 变量&#xff08;Variables&#xff09;…...

【解决】k8s使用kubeadm初始化集群失败问题整理

执行提示命令&#xff0c;查看报错信息 journalctl -xeu kubelet1、错误&#xff1a;running with swap on is no 报错 "command failed" err"failed to run Kubelet: running with swap on is no 解决&#xff1a; swap未禁用&#xff0c;需要禁用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,附视频讲解与代码下载

引言&#xff1a; 在数据可视化的世界里&#xff0c;ECharts凭借其丰富的图表类型和强大的配置能力&#xff0c;成为了众多开发者的首选。今天&#xff0c;我将带大家一起实现一个柱状图图表&#xff0c;通过该图表我们可以直观地展示和分析数据。此外&#xff0c;我还将提供…...

【新人系列】Python 入门(十六):正则表达式

✍ 个人博客&#xff1a;https://blog.csdn.net/Newin2020?typeblog &#x1f4dd; 专栏地址&#xff1a;https://blog.csdn.net/newin2020/category_12801353.html &#x1f4e3; 专栏定位&#xff1a;为 0 基础刚入门 Python 的小伙伴提供详细的讲解&#xff0c;也欢迎大佬们…...

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”错误

今天&#xff0c;在windows系统上&#xff0c;打开VMware WorkStation v15软件里的虚拟机&#xff0c;弹出"Intel VT-x处于禁用状态"错误&#xff0c;如图(1)所示&#xff1a; 图(1) 虚拟机报"Intel VT-x"错误 问题原因&#xff1a;当前电脑的BIOS没有开启…...

NiceGUI `ui.table` 基础

NiceGUI ui.table 基础 ui.table 是 NiceGUI 提供的一个组件&#xff0c;用于在页面上展示数据表格 基本概念 官方简介 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 中&#xff0c;动态绑定&#xff08;Dynamic Binding&#xff09;是通过 虚函数&#xff08;virtual function&#xff09; 和 多态性&#xff08;polymorphism&#xff09; 来实现的。这是面向对象编程的重要特性之一&#xff0c;它允许程序在运行时根据对象的实际类型调…...

微服务-01

1.认识微服务 1.1 单体架构 单体架构&#xff08;monolithic structure&#xff09;&#xff1a;顾名思义&#xff0c;整个项目中所有功能模块都在一个工程中开发&#xff1b;项目部署时需要对所有模块一起编译、打包&#xff1b;项目的架构设计、开发模式都非常简单。 当项目…...

这是一个vue3 + scss的数字滚动效果

介绍: 当数字变化时&#xff0c;只改变变化的数字位&#xff0c;其余的不变&#xff0c;可以递增、递减、骤变、负数也可以&#xff0c;但是样式要根据具体的项目需求去改&#xff1b; 效果1、增加数字&#xff1a; 效果2、减少数字&#xff1a; 使用方法&#xff1a; <te…...

数字证书管理工具 openssl keytool

OPENSSL 命令 openssl command [ command_opts ] [ command_args ] 常用command: version 用于查看版本信息 enc 用于加解密 ciphers 列出加密套件 genrsa 用于生成私钥 -des|-des3|-idea&#xff1a;用来加密私钥文件的三种对称加密算法。 rsa …...

Polars数据聚合与旋转实战教程

在这篇博文中&#xff0c;我们的目标是解决数据爱好者提出的一个常见问题&#xff1a;如何有效地从Polars DataFrame中创建汇总视图&#xff0c;以便在不同时间段或类别之间轻松进行比较。我们将使用一个实际的数据集示例来探索实现这一目标的各种方法。 Polars简介 Polars 是…...

引用类型集合的深拷贝,无需手动写循环:Apache Commons Lang (SerializationUtils)

在java中&#xff0c;我们如果想要对引用类型的集合进行深拷贝。有一种方式&#xff0c;就是调用SerializationUtils Apache Commons Lang (SerializationUtils) Apache Commons Lang 提供了 SerializationUtils 类&#xff0c;可以利用 Java 的序列化机制来进行集合及其元素…...

HTML、CSS表格的斜表头样式设置title 画对角线

我里面有用到layui框架的影响&#xff0c;实际根据你自己的框架来小调下就可以 效果如下 上代码 <!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 若是拉取不了&#xff0c;可以配置下 docker 源 2. 查看是否安装成功 docker images 下图就是成功了 3.创建mysql专用目录、数据挂载目录、配置文件目录 &#xff0c;演示目录在于/home/下 //命令逐条执行cd /home/ mkdir mysql …...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...