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

二叉树最大宽度

文章目录

  • 前言
  • 二叉树最大宽度
    • 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 &#xff0c;返回树的 最大宽度 。 树的 最大宽度 是所有层中最大的 宽度 。 每一层的 宽度 被定义为该层最左和最右的非空节点&#xff08;即…...

React@16.x(24)自定义HOOK

目录 1&#xff0c;介绍2&#xff0c;简单举例2.1&#xff0c;获取数据1.2&#xff0c;计时器 2&#xff0c;自定义 HOOK 相比类组件 1&#xff0c;介绍 将一些常用的&#xff0c;跨组件的函数抽离&#xff0c;做成公共函数也就是 HOOK。自定义HOOK需要按照HOOK的规则来实现&a…...

群体优化算法----树蛙优化算法介绍以及应用于资源分配示例

介绍 树蛙优化算法&#xff08;Tree Frog Optimization Algorithm, TFO&#xff09;是一种基于群体智能的优化算法&#xff0c;模拟了树蛙在自然环境中的跳跃和觅食行为。该算法通过模拟树蛙在树枝间的跳跃来寻找最优解&#xff0c;属于近年来发展起来的自然启发式算法的一种 …...

常见汇编指令

下面是一些包含汇编指令 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 概述 概念&#xff1a;约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据。目的&#xff1a;保证数据库中数据的正确、有效性和完整性。分类&#xff1a; 4.2 约束演示 根据需求&…...

Redis实战篇02

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

怎么用PHP语言实现远程控制两路照明开关

怎么用PHP语言实现远程控制两路开关呢&#xff1f; 本文描述了使用PHP语言调用HTTP接口&#xff0c;实现控制两路开关&#xff0c;两路开关可控制两路照明、排风扇等电器。 可选用产品&#xff1a;可根据实际场景需求&#xff0c;选择对应的规格 序号设备名称厂商1智能WiFi墙…...

Docker面试整理-什么是多阶段构建?它的好处是什么?

多阶段构建是 Docker 在 Dockerfile 中引入的一个功能,允许你在单个 Dockerfile 中使用多个构建阶段,但最终只生成一个轻量级的镜像。这是通过在一个 Dockerfile 中定义多个 FROM 指令来实现的,每个 FROM 指令都可以使用不同的基础镜像,并开始一个新的构建阶段。 多阶段构建…...

ENSP校园网设计实验

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

【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.三种配置文件 问题导入 框架常见的配置文件有哪几种形式&#xff1f; 比如&#xf…...

华为坤灵路由器初始化的几个坑,含NAT配置

1、aaa密码复杂度修改&#xff1a; #使能设备对密码进行四选三复杂度检查功能。 <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 中&#xff0c;文档转换器是一种在将文档提供给其他 Langchain 组件之前对其进行处理的工具。通过清理、处理和转换文档&#xff0c;这些工具可确保 LLM 和其他 Langchain 组件以优化其性能的格式接收数据。 上一章我们了解了文档加载器&#xff0c;加载完文档之…...

请求 响应

在web的前后端分离开发过程中&#xff0c;前端发送请求给后端&#xff0c;后端接收请求&#xff0c;响应数据给前端 请求 前端发送数据进行请求 简单参数 原始方式 在原始的web程序中&#xff0c;获取请求参数&#xff0c;需要通过HttpServletRequest 对象手动获取。 代码…...

技术周总结2024.06.03~06.09(K8S HikariCP数据库连接池)

文章目录 一、06.05 周三1.1) 问题01: 容器领域&#xff0c;Docker与 K8S的区别和联系Docker主要功能和特点&#xff1a;使用场景&#xff1a; Kubernetes (K8S)主要功能和特点&#xff1a;使用场景&#xff1a; 联系和区别联系&#xff1a;区别&#xff1a; 结合使用总结 二、…...

【JavaScript】了解 Sass:现代 CSS 的强大预处理器

我已经从你的 全世界路过 像一颗流星 划过命运 的天空 很多话忍住了 不能说出口 珍藏在 我的心中 只留下一些回忆 &#x1f3b5; 牛奶咖啡《从你的全世界路过》 在前端开发领域&#xff0c;CSS 是必不可少的样式表语言。然而&#xff0c;随着项目复杂度的…...

下载安装Thonny并烧录MicroPython固件至ESP32

Thonny介绍 一、Thonny的基本特点 面向初学者&#xff1a;Thonny的设计初衷是为了帮助Python初学者更轻松、更快速地入门编程。它提供了直观易懂的用户界面和丰富的功能&#xff0c;降低了编程的门槛。轻量级&#xff1a;作为一款轻量级的IDE&#xff0c;Thonny不会占用过多的…...

YOLOv5改进 | 主干网络 | 将主干网络替换为轻量化的ShuffleNetv2【原理 + 完整代码】

&#x1f4a1;&#x1f4a1;&#x1f4a1;本专栏所有程序均经过测试&#xff0c;可成功执行&#x1f4a1;&#x1f4a1;&#x1f4a1; 目标检测是计算机视觉中一个重要的下游任务。对于边缘盒子的计算平台来说&#xff0c;一个大型模型很难实现实时检测的要求。基于一系列消融…...

LeetCode:字母异位词分组

文章收录于LeetCode专栏 LeetCode地址 字母异位词分组 题目 给定一个字符串数组&#xff0c;将字母异位词组合在一起。字母异位词指字母相同&#xff0c;但排列不同的字符串。所有输入均为小写字母&#xff0c;且不考虑答案输出的顺序。   示例1&#xff1a; 输入: strs [“…...

技术与业务的完美融合:大数据BI如何真正提升业务价值

数据分析有一点经典案例 沃尔玛的啤酒和尿布案例 开始做BI的时候&#xff0c;大家肯定都看过书&#xff0c;那么一定也看过一个经典的案例&#xff0c;就是沃尔玛的啤酒和尿布的案例。这个案例确实很经典&#xff0c;但其实是一个失败的案例。为什么这么说呢&#xff1f;很明显…...

计网复习资料

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

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

深入解析 ReentrantLock:原理、公平锁与非公平锁的较量

ReentrantLock 是 Java 中 java.util.concurrent.locks 包下的一个重要类,用于实现线程同步,支持可重入性,并且可以选择公平锁或非公平锁的实现方式。下面将详细介绍 ReentrantLock 的实现原理以及公平锁和非公平锁的区别。 ReentrantLock 实现原理 基本架构 ReentrantLo…...

python可视化:俄乌战争时间线关键节点与深层原因

俄乌战争时间线可视化分析&#xff1a;关键节点与深层原因 俄乌战争是21世纪欧洲最具影响力的地缘政治冲突之一&#xff0c;自2022年2月爆发以来已持续超过3年。 本文将通过Python可视化工具&#xff0c;系统分析这场战争的时间线、关键节点及其背后的深层原因&#xff0c;全面…...

21-Oracle 23 ai-Automatic SQL Plan Management(SPM)

小伙伴们&#xff0c;有没有迁移数据库完毕后或是突然某一天在同一个实例上同样的SQL&#xff0c; 性能不一样了、业务反馈卡顿、业务超时等各种匪夷所思的现状。 于是SPM定位开始&#xff0c;OCM考试中SPM必考。 其他的AWR、ASH、SQLHC、SQLT、SQL profile等换作下一个话题…...

【threejs】每天一个小案例讲解:创建基本的3D场景

代码仓 GitHub - TiffanyHoo/three_practices: Learning three.js together! 可自行clone&#xff0c;无需安装依赖&#xff0c;直接liver-server运行/直接打开chapter01中的html文件 运行效果图 知识要点 核心三要素 场景&#xff08;Scene&#xff09; 使用 THREE.Scene(…...

Linux--vsFTP配置篇

一、vsFTP 简介 vsftpd&#xff08;Very Secure FTP Daemon&#xff09;是 Linux 下常用的 FTP 服务程序&#xff0c;具有安全性高、效率高和稳定性好等特点。支持匿名访问、本地用户登录、虚拟用户等多种认证方式&#xff0c;并可灵活控制权限。 二、安装与启动 1. 检查是否已…...