【LeetCode每日一题】——662.二叉树最大宽度
文章目录
- 一【题目类别】
- 二【题目难度】
- 三【题目编号】
- 四【题目描述】
- 五【题目示例】
- 六【题目提示】
- 七【解题思路】
- 八【时间频度】
- 九【代码实现】
- 十【提交结果】
一【题目类别】
- 广度优先搜索
二【题目难度】
- 中等
三【题目编号】
- 662.二叉树最大宽度
四【题目描述】
- 给你一棵二叉树的根节点
root
,返回树的 最大宽度 。 - 树的 最大宽度 是所有层中最大的 宽度 。
- 每一层的 宽度 被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的
null
节点,这些null
节点也计入长度。 - 题目数据保证答案将会在
32
位 带符号整数范围内。
五【题目示例】
-
示例 1:
- 输入:root = [1,3,2,5,3,null,9]
- 输出:4
- 解释:最大宽度出现在树的第 3 层,宽度为 4 (5,3,null,9) 。
-
示例 2:
- 输入:root = [1,3,2,5,null,null,9,6,null,7]
- 输出:7
- 解释:最大宽度出现在树的第 4 层,宽度为 7 (6,null,null,null,null,null,7) 。
-
示例 3:
- 输入:root = [1,3,2,5]
- 输出:2
- 解释:最大宽度出现在树的第 2 层,宽度为 2 (3,2) 。
六【题目提示】
- 树中节点的数目范围是
[1, 3000]
100 <= Node.val <= 100
七【解题思路】
- 其实这道题就是二叉树的层序遍历的变种
- 值得注意的是需要利用完全二叉树的性质
- 在完全二叉树中,可以将其节点存储到数组中,并且对于序号为
i
的节点(节点编号从1开始),其- 左子节点的序号为
i * 2
- 右子节点的序号为
i * 2 + 1
- 左子节点的序号为
- 利用以上性质,我们可以将每一层的二叉树的节点编号,用编号值计算每一层的宽度
- 当计算出每一层的宽度后,就可以计算得到整个二叉树的最大宽度
- 在完全二叉树中,可以将其节点存储到数组中,并且对于序号为
- 具体细节请参考下面的代码
八【时间频度】
- 时间复杂度: O ( n ) O(n) O(n), n n n为传入的二叉树的节点个数
- 空间复杂度: O ( n ) O(n) O(n), n n n为传入的二叉树的节点个数
九【代码实现】
- Java语言版
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/class Solution {public int widthOfBinaryTree(TreeNode root) {// 最小宽度为1int res = 1;// 初始化队列,queue用于存储当前层节点List<Pair<TreeNode, Integer>> queue = new ArrayList<Pair<TreeNode, Integer>>();queue.add(new Pair<TreeNode, Integer>(root, 1));// 使用广度优先遍历算法计算二叉树的最大高度while (!queue.isEmpty()) {// temp用于存储下一层节点List<Pair<TreeNode, Integer>> temp = new ArrayList<Pair<TreeNode, Integer>>();for (Pair<TreeNode, Integer> pair : queue) {TreeNode node = pair.getKey();int index = pair.getValue();if (node.left != null) {temp.add(new Pair<TreeNode, Integer>(node.left, index * 2));}if (node.right != null) {temp.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));}}// 计算二叉树的最大宽度res = Math.max(res, queue.get(queue.size() - 1).getValue() - queue.get(0).getValue() + 1);queue = temp;}// 返回结果return res;}
}
- Python语言版
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = rightclass Solution:def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:# 最小宽度为1res = 1# 初始化队列,queue用于存储当前层节点queue = [[root, 1]]# 使用广度优先遍历算法计算二叉树的最大高度while queue:# temp用于存储下一层节点temp = []for node, index in queue:if node.left:temp.append([node.left, index * 2])if node.right:temp.append([node.right, index * 2 + 1])# 计算二叉树的最大宽度res = max(res, queue[-1][1] - queue[0][1] + 1)queue = temp# 返回结果return res
- C语言版
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/// 节点最多3000个
#define MAX_NODE_SIZE 3000// 比较大小
#define MAX(a, b) ((a) > (b) ? (a) : (b));// 利用完全二叉树的性质存储二叉树,node保留了节点的左右子树的关系,index记录节点(在数组中)的位置(索引)
typedef struct
{struct TreeNode* node;unsigned long long index;
} levelNode;int widthOfBinaryTree(struct TreeNode* root)
{// 最小宽度为1unsigned long long res = 1;// 初始化队列,queue用于存储当前层节点,temp用于存储下一层节点levelNode* queue = (levelNode*)malloc(sizeof(levelNode) * MAX_NODE_SIZE);levelNode* temp = (levelNode*)malloc(sizeof(levelNode) * MAX_NODE_SIZE);int queueSize = 0;int tempSize = 0;// 根节点入队列queue[queueSize].node = root;queue[queueSize++].index = 1LL;// 使用广度优先遍历算法计算二叉树的最大宽度while (queueSize > 0){// 将当前节点的所有下一层节点按照完全二叉树的索引值存储tempSize = 0;for (int i = 0; i < queueSize; i++){if (queue[i].node->left){temp[tempSize].node = queue[i].node->left;temp[tempSize++].index = queue[i].index * 2;}if (queue[i].node->right){temp[tempSize].node = queue[i].node->right;temp[tempSize++].index = queue[i].index * 2 + 1;} }// 计算二叉树的最大宽度res = MAX(res, queue[queueSize - 1].index - queue[0].index + 1);// 将存储当前层节点信息的队列重新赋值为存储好的下一层节点的信息队列queueSize = tempSize;levelNode* change = queue;queue = temp;temp = change;}// 返回结果return res;
}
十【提交结果】
-
Java语言版
-
Python语言版
-
C语言版
相关文章:

【LeetCode每日一题】——662.二叉树最大宽度
文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 广度优先搜索 二【题目难度】 中等 三【题目编号】 662.二叉树最大宽度 四【题目描述】 给…...

第二十三节、血量更新逻辑的实现
一、创建代码 引入命名空间 using UnityEngine.UI; 调用UI必须有这个代码 二、ScriptObject类 1、是一个持久化存储文件的类型 接收所有的事件方法 先继承SO类,然后创建项目菜单 2、进行订阅 放入事件类,关联代码,即可进行广播 传递给这…...
Spring Authorization Server 认证服务器搭建
Spring Authorization Server实现了oauth2和oidc,最近有了解相关技术的需求,所以就尝试着进行了基本的环境搭建和技术测试,目前只测试了授权码模式,做一个记录,后续需要用时方便查找和参考。 1. 版本要求 Spring Authorization Server 版本:1.3.1 JDK 版本:17 Spring B…...

秋招突击——8/15——知识补充——垃圾回收机制
文章目录 引言正文指针引用可达性分析算法垃圾回收算法标记清除算法标记整理算法复制分代收集 垃圾收集器Serial收集器ParNew并行收集器Parallel Scavenge吞吐量优先收集器Serial Old老年代收集器Parallel old收集器CMS收集器G1收集器(Garbage First垃圾优先&#x…...

【iOS】UITableViewCell的重用问题解决方法
我自己在实验中对cell的重用总结如下: 非自定义Cell和非自定义cell的复用情况一样: 第一次加载创建tableView的时候,是屏幕上最多也显示几行cell就先创建几个cell,此时复用池里什么都没有开始下滑tableView,刚开始滑…...
开发一个微信小程序商城需要哪些技术栈
开发一个小程序商城需要掌握以下技术栈: 前端技术:包括HTML、CSS和JavaScript,用于定义商城的页面结构、样式设计和交互功能。 微信小程序专用技术:如WXML、WXSS、JavaScript和JSON,用于描述小程…...

望繁信科技荣膺上海市浦东新区博士后创新实践基地称号
近日,上海望繁信科技有限公司(简称“望繁信科技”)凭借在大数据流程智能领域的卓越表现,成功入选上海市浦东新区博士后创新实践基地。这一荣誉不仅是对望繁信科技创新能力和技术实力的高度认可,也标志着公司在推动产学…...

Nginx--代理与负载均衡(扩展nginx配置7层协议及4层协议方法、会话保持)
前言:本博客仅作记录学习使用,部分图片出自网络,如有侵犯您的权益,请联系删除 一、代理原理 1、反向代理产生的背景 单个服务器的处理客户端(用户)请求能力有一个极限,当接入请求过多时&#…...

Ubuntu20.4 系统安装后无wifi图标
0. 问题排查 1.检查 BIOS 设置: 有时候,无线网卡可能在 BIOS 中被禁用。重启电脑,进入 BIOS 设置,确保无线网卡选项是启用的。 2.检查硬件开关: 检查您的笔记本电脑是否有物理开关或键盘快捷键来启用或禁用无线网卡。 3.在软件更新中切换…...

牛客网SQL进阶135 :每个6/7级用户活跃情况
每个67级用户活跃情况_牛客题霸_牛客网 0 问题描述 基于用户信息表user_info、、试卷作答记录表exam_record、题目练习记录表practice_record,统计 每个6/7级用户总活跃月份数、2021年活跃天数、2021年试卷作答活跃天数、2021年答题活跃天数,结果 按照总…...
SQLite3使用接口写入二进制文件
使用接口的方式写入二进制文件 ,有二种方案。 一、全部文件 一次性写下到数据中 使用sqlite3_bind_blob接口 FILE* fpfopen("user.bmp","rb"); iLenfread(buffer,1,65535,fp); fclose(fp);sqlite3_prepare(pDB,"insert into user values …...
在复杂的数据库架构中,如何优化 SQL 查询以提高性能和减少资源消耗?
在优化 SQL 查询以提高性能和减少资源消耗时,可以考虑以下几个方面: 使用索引:为经常被查询的列创建索引,可以大大加快查询速度。同时,避免过多的索引,因为过多的索引会增加写入操作的开销。 编写高效的查…...

【HarmonyOS】端云一体化初始化项目
简介 端云一体化开发是HarmonyOS对云端开发的支持、实现端云联动。云开发服务提供了云函数、云数据库、云存储等服务,可以使开发者专注于应用的业务逻辑开发,无需关注基础设施,例如:服务器、操作系统等问题。 因此,…...
LLM之KG:利用大语言模型(LLM)对文本语料提取概念和概念之间的语义关系进而实现自动构建知识图谱
LLM之KG:利用大语言模型(LLM)对文本语料提取概念和概念之间的语义关系进而实现自动构建知识图谱 目录 ML之KG:基于MovieLens电影评分数据集利用基于知识图谱的推荐算法(networkx+基于路径相似度的方法)实现对用户进行Top电影推荐案例 LLMs之AutoKG:《大型语言模型在知识图…...
Spring Security 6如何使用?
Spring Security 6 是一个功能强大且高度可定制的身份验证和访问控制框架,它专注于为基于Java的应用程序提供全面的安全解决方案。以下是对Spring Security 6的详细解析: 一、核心功能 身份验证(Authentication): 验…...

PyTorch深度学习快速入门教程--学习笔记
目录 P4 PyCharm和Jupyter的对比 P5 PyTorch加载数据 P6 Dataset类代码实现 P7 Tensorboard 写日志 读取日志文件 Tensorboard 读图片 P10 Transforms使用 Transforms用途 常见的Transforms工具 P14 torchvision数据集使用 P15 Dataloader使用 P16 nn.Module模块使…...
SQLALchemy 分组过滤、子查询
SQLALchemy 分组过滤、子查询 分组和过滤(Group By Having)示例:使用ORM示例:使用SQLAlchemy Core子查询(Subquery)SQLAlchemy 是一个流行的 SQL 工具包和对象关系映射(ORM)库,用于 Python 应用程序。它允许你以 Pythonic 的方式使用 SQL 数据库,同时提供了强大的查询…...
华为od(D卷) 环中最长子串/字符成环找偶数LOX
文章目录 题目描述输入描述输出描述示例1示例2示例3思路代码 题目描述 给你一个字符串 s,字符串 s 首尾相连成一个环形,请你在环中找出 ‘l’、‘o’、‘x’ 字符都恰好出现了偶数次最长子字符串的长度。 输入描述 输入是一串小写的字母组成的字符串 …...

机器学习--常见算法总结
有监督学习算法 1. 线性回归算法 概念:线性回归是一种统计方法,用于预测一个变量(因变量)与一个或多个自变量(特征变量)之间的关系。目标是通过线性方程建立自变量和因变量之间的关系模型。 作用&#x…...

QT 网络聊天室简易版
视频:qt开发网络聊天w室软件3.4界面开发_哔哩哔哩_bilibili 目录 UI部分 设计稿图 放置控件 界面美化 拖动窗体 设置界面 网络部分 配置对话框 多项目结果和服务器端设计 客户端框架开发 UI部分 设计稿图 放置控件 界面美化 现在我们把窗体自带的标题栏给去了,用我们自…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...

R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
如何配置一个sql server使得其它用户可以通过excel odbc获取数据
要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据,你需要完成以下配置步骤: ✅ 一、在 SQL Server 端配置(服务器设置) 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到:SQL Server 网络配…...
LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》
🧠 LangChain 中 TextSplitter 的使用详解:从基础到进阶(附代码) 一、前言 在处理大规模文本数据时,特别是在构建知识库或进行大模型训练与推理时,文本切分(Text Splitting) 是一个…...
【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解
一、前言 在HarmonyOS 5的应用开发模型中,featureAbility是旧版FA模型(Feature Ability)的用法,Stage模型已采用全新的应用架构,推荐使用组件化的上下文获取方式,而非依赖featureAbility。 FA大概是API7之…...