二叉树最大宽度
文章目录
- 前言
- 二叉树最大宽度
- 1.题目解析
- 2.算法原理
- 3.代码编写
- 总结
前言
二叉树最大宽度
1.题目解析
给你一棵二叉树的根节点 root ,返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的 null 节点,这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
输入:root = [1,3,2,5,3,null,9]
输出:4
解释:最大宽度出现在树的第 3 层,宽度为 4 (5,3,null,9) 。
输入:root = [1,3,2,5,null,null,9,6,null,7]
输出:7
解释:最大宽度出现在树的第 4 层,宽度为 7 (6,null,null,null,null,null,7) 。
2.算法原理
思路一:
统计每一层的最大宽度,优先想到的就是层序遍历,把当前层节点全部存在队列中,利用队列的长度计算每一层的宽度就可以统计出最大宽度。
空节点也是现需要计算的,将空节点也存放在队列中。
但是在极端场景下,最左边一条长链,最右边一条长链,我们就需要几亿个节点,超出内存限制。
这个思路是错误的
思路二:
依旧是利⽤层序遍历,但是这⼀次队列⾥⾯不单单存结点信息,并且还存储当前结点如果在数组中存储所对应的下标(在我们学习数据结构 - 堆的时候,计算左右孩⼦的⽅式)这样我们计算每⼀层宽度的时候,⽆需考虑空节点,只需将当层结点的左右结点的下标相减再加 1 即可。
但是,这⾥有个细节问题:如果⼆叉树的层数⾮常恐怖的话,我们任何⼀种数据类型都不能存下下标
的值。但是没有问题,因为
• 我们数据的存储是⼀个环形的结构;
• 并且题⽬说明,数据的范围在 int 这个类型的最⼤值的范围之内,因此不会超出⼀圈;
• 因此,如果是求差值的话,我们⽆需考虑溢出的情况。
3.代码编写
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {queue<pair<TreeNode*,unsigned int>>q;if(root==nullptr){return 0;}q.push({root,1});unsigned int maxlen=1;while(!q.empty()){int n=q.size();unsigned int begin=q.front().second;unsigned int end=q.back().second;maxlen=max(maxlen,end-begin+1);for(int i=0;i<n;i++){TreeNode*t=q.front().first;if(t->left){q.push({t->left,q.front().second*2});}if(t->right){q.push({t->right,q.front().second*2+1});}q.pop();}}return maxlen;}
};
总结
以上就是今天要讲的内容。希望对大家的学习有所帮助,仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘
相关文章:

二叉树最大宽度
文章目录 前言二叉树最大宽度1.题目解析2.算法原理3.代码编写 总结 前言 二叉树最大宽度 1.题目解析 给你一棵二叉树的根节点 root ,返回树的 最大宽度 。 树的 最大宽度 是所有层中最大的 宽度 。 每一层的 宽度 被定义为该层最左和最右的非空节点(即…...
React@16.x(24)自定义HOOK
目录 1,介绍2,简单举例2.1,获取数据1.2,计时器 2,自定义 HOOK 相比类组件 1,介绍 将一些常用的,跨组件的函数抽离,做成公共函数也就是 HOOK。自定义HOOK需要按照HOOK的规则来实现&a…...

群体优化算法----树蛙优化算法介绍以及应用于资源分配示例
介绍 树蛙优化算法(Tree Frog Optimization Algorithm, TFO)是一种基于群体智能的优化算法,模拟了树蛙在自然环境中的跳跃和觅食行为。该算法通过模拟树蛙在树枝间的跳跃来寻找最优解,属于近年来发展起来的自然启发式算法的一种 …...
常见汇编指令
下面是一些包含汇编指令 MOV、PUSH、POP、LEA、LDS、ADD、ADC、INC、SUB、SBB、DEC、CMP、MUL、DIV、AND、OR、XOR、NOT、TEST、SHL、SAL、SHR、SAR、ROL、ROR、RCL、RCR、LODS、MOVS 的例题。这些例题展示了每条指令的用法及其作用。 1. MOV 指令 MOV AX, BX ; 将寄存器 B…...

Mysql学习(七)——约束
文章目录 四、约束4.1 概述4.2 约束演示4.3 外键约束 总结 四、约束 4.1 概述 概念:约束是作用于表中字段上的规则,用于限制存储在表中的数据。目的:保证数据库中数据的正确、有效性和完整性。分类: 4.2 约束演示 根据需求&…...

Redis实战篇02
1.分布式锁Redisson 简单介绍: 使用setnx可能会出现的极端问题: Redisson的简介: 简单的使用: 业务代码的改造: private void handleVoucherOrder(VoucherOrder voucherOrder) {Long userId voucherOrder.getUserI…...

怎么用PHP语言实现远程控制两路照明开关
怎么用PHP语言实现远程控制两路开关呢? 本文描述了使用PHP语言调用HTTP接口,实现控制两路开关,两路开关可控制两路照明、排风扇等电器。 可选用产品:可根据实际场景需求,选择对应的规格 序号设备名称厂商1智能WiFi墙…...
Docker面试整理-什么是多阶段构建?它的好处是什么?
多阶段构建是 Docker 在 Dockerfile 中引入的一个功能,允许你在单个 Dockerfile 中使用多个构建阶段,但最终只生成一个轻量级的镜像。这是通过在一个 Dockerfile 中定义多个 FROM 指令来实现的,每个 FROM 指令都可以使用不同的基础镜像,并开始一个新的构建阶段。 多阶段构建…...

ENSP校园网设计实验
前言 哈喽,我是ICT大龙。本次更新了使用ENSP仿真软件设计校园网实验。时间比较着急,可能会有错误,欢迎大家指出。 获取本次工程文件方式在文章结束部分。 拓扑设计 拓扑介绍---A校区 如图,XYZ大学校园网设计分为3部分࿰…...

【Spring框架全系列】SpringBoot_3种配置文件_yml语法_多环境开发配置_配置文件分类(详细)
文章目录 1.三种配置文件2. yaml语法2.1 yaml语法规则2.2 yaml数组数据2.3 yaml数据读取 3. 多环境开发配置3.1 多环境启动配置3.2 多环境启动命令格式3.3 多环境开发控制 4. 配置文件分类 1.三种配置文件 问题导入 框架常见的配置文件有哪几种形式? 比如…...
华为坤灵路由器初始化的几个坑,含NAT配置
1、aaa密码复杂度修改: #使能设备对密码进行四选三复杂度检查功能。 <HUAWEI>system-view [HUAWEI]aaa [HUAWEI-aaa]local-aaa-user password policy administrator [HUAWEI-aaa-lupp-admin]password complexity three-of-kinds 2、本地用户名长度必须大…...
【RAG入门教程04】Langchian的文档切分
在 Langchain 中,文档转换器是一种在将文档提供给其他 Langchain 组件之前对其进行处理的工具。通过清理、处理和转换文档,这些工具可确保 LLM 和其他 Langchain 组件以优化其性能的格式接收数据。 上一章我们了解了文档加载器,加载完文档之…...

请求 响应
在web的前后端分离开发过程中,前端发送请求给后端,后端接收请求,响应数据给前端 请求 前端发送数据进行请求 简单参数 原始方式 在原始的web程序中,获取请求参数,需要通过HttpServletRequest 对象手动获取。 代码…...
技术周总结2024.06.03~06.09(K8S HikariCP数据库连接池)
文章目录 一、06.05 周三1.1) 问题01: 容器领域,Docker与 K8S的区别和联系Docker主要功能和特点:使用场景: Kubernetes (K8S)主要功能和特点:使用场景: 联系和区别联系:区别: 结合使用总结 二、…...
【JavaScript】了解 Sass:现代 CSS 的强大预处理器
我已经从你的 全世界路过 像一颗流星 划过命运 的天空 很多话忍住了 不能说出口 珍藏在 我的心中 只留下一些回忆 🎵 牛奶咖啡《从你的全世界路过》 在前端开发领域,CSS 是必不可少的样式表语言。然而,随着项目复杂度的…...

下载安装Thonny并烧录MicroPython固件至ESP32
Thonny介绍 一、Thonny的基本特点 面向初学者:Thonny的设计初衷是为了帮助Python初学者更轻松、更快速地入门编程。它提供了直观易懂的用户界面和丰富的功能,降低了编程的门槛。轻量级:作为一款轻量级的IDE,Thonny不会占用过多的…...

YOLOv5改进 | 主干网络 | 将主干网络替换为轻量化的ShuffleNetv2【原理 + 完整代码】
💡💡💡本专栏所有程序均经过测试,可成功执行💡💡💡 目标检测是计算机视觉中一个重要的下游任务。对于边缘盒子的计算平台来说,一个大型模型很难实现实时检测的要求。基于一系列消融…...
LeetCode:字母异位词分组
文章收录于LeetCode专栏 LeetCode地址 字母异位词分组 题目 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。所有输入均为小写字母,且不考虑答案输出的顺序。 示例1: 输入: strs [“…...

技术与业务的完美融合:大数据BI如何真正提升业务价值
数据分析有一点经典案例 沃尔玛的啤酒和尿布案例 开始做BI的时候,大家肯定都看过书,那么一定也看过一个经典的案例,就是沃尔玛的啤酒和尿布的案例。这个案例确实很经典,但其实是一个失败的案例。为什么这么说呢?很明显…...

计网复习资料
一、选择题(每题2分,共40分) 1. Internet 网络本质上属于( )网络。 A.电路交换 B.报文交换 C.分组交换 D.虚电路 2.在 OSI 参考模型中,自下而上第一个提供端到端服务的是( )。 A.数据链路层 B.传输…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...

Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...