代码随想录-51-110.平衡二叉树
目录
- 前言
- 题目
- 1.求高度和深度的区别
- 节点的高度
- 节点的深度
- 2. 本题思路分析:
- 3. 算法实现
- 4. pop函数的算法复杂度
- 5. 算法坑点
前言
在本科毕设结束后,我开始刷卡哥的“代码随想录”,每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接
题目
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。


1.求高度和深度的区别
节点的高度
求节点的高度指的是该节点到叶子节点的最长简单路径的节点数,
求节点的高度,递归方法时记得使用后序遍历
但是求根节点的高度就是求二叉树的最大深度
节点的深度
求节点的深度指的是根节点到该节点的最长简单路径的节点数
求节点的深度,递归方法时记得使用前序遍历
2. 本题思路分析:
- 使用后续遍历,因为求的是节点的高度,求出节点的左右孩子的高度,进行比较,如果差值大于1则代表不是平衡二叉树,向父节点返回-1,告知父节点此树不为平衡二叉树;
- 否则返回当前节点的高度,当前节点的高度是,左右子树的最大值+1就是当前节点的高度。
3. 算法实现
- 代码:
//递归法(后序遍历)因为是求高度,所以是后序遍历
//求高度,所以使用后序遍历
public boolean isBalanced(TreeNode root) {return getHeightOfTree(root) == -1 ? false :true;
}
//递归三部曲
//1.确定返回值和参数 返回值是深度 参数是以当前节点 如果是平衡二叉树则返回树的高度,否则返回-1
//2.确定返回条件
//3.确定单层递归逻辑
public int getHeightOfTree(TreeNode root){if(root == null){return 0;}int leftHeight = getHeightOfTree(root.left);if(leftHeight == -1){//左子树不为平衡二叉树return -1;}int rightHeight = getHeightOfTree(root.right);if(rightHeight == -1){//右子树不为平衡二叉树return -1;}if(Math.abs(leftHeight - rightHeight) <= 1){//该节点为根节点的树不为平衡二叉树return 1 + Math.max(leftHeight , rightHeight); }else{return -1;}}
4. pop函数的算法复杂度
n为总结点数
时间复杂度:O(log n × log n)
空间复杂度:O(log n)
5. 算法坑点
暂无
相关文章:
代码随想录-51-110.平衡二叉树
目录前言题目1.求高度和深度的区别节点的高度节点的深度2. 本题思路分析:3. 算法实现4. pop函数的算法复杂度5. 算法坑点前言 在本科毕设结束后,我开始刷卡哥的“代码随想录”,每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专…...
项目实战典型案例27——对生产环境以及生产数据的敬畏之心
对生产环境以及生产数据的敬畏之心一:背景介绍总结升华一:背景介绍 本篇博客是对项目开发中出现的对生产环境以及生产数据的敬畏之心行的总结并进行的改进。目的是将经历转变为自己的经验。通过博客的方式分享给大家,大家一起共同进步和提高…...
如何查找你的IP地址?通过IP地址能直接定位到你家!
我们ip地址分为A、B、C、D、E共5类,每一类地址范围不同,从A到Eip地址范围依次递减,其中哦,D和E是保留地址,我们用不了。A、B、C3类地址很多都被美国这样的西方国家分走了,而留给我们的就剩有限的地址了&…...
Containers--array类
Array 类 简介 Array 类是一个固定大小的数组,它的大小在编译时就已经确定了。Array 类的大小是固定的,因此它的大小不能改变。 数组是固定大小的序列容器:它们以严格的线性顺序保存特定数量的元素。 在内部,数组除了包含的元素之外不保留…...
LinqConnect兼容性并支持Visual Studio 2022版本
LinqConnect兼容性并支持Visual Studio 2022版本 现在支持Microsoft Visual Studio 2022版本17.5预览版。 添加了Microsoft.NET 7兼容性。 共享代码-共享相同的代码,以便在不同的平台上处理数据。LinqConnect是一种数据库连接解决方案,适用于不同的基于.…...
流量监管与整形
流量监管与整形概览流量监管介绍流量监管令牌桶流量监管的具体实现单桶单速流量监管双桶单速流量监管双桶双速流量监管流量整形介绍GTS(Generic Traffic Shaping)LR(Line Rate)流量整形与流量监管的区别概览 流量整形是对报文的速…...
详解init 容器
什么是init容器 init 容器是一种特殊容器,在 Pod 内的应用容器启动之前运行。Init 容器可以包括一些应用镜像中不存在的实用工具和安装脚本。 你可以在 Pod 的规约中与用来描述应用容器的 containers 数组平行的位置指定 Init 容器 每个 Pod 中可以包含多个容器&…...
RequestResponseBodyMethodProcessor
既是一个参数解析器,也是一个返回结果处理器。 1.持有消息转换器的集合 protected final List<HttpMessageConverter<?>> messageConverters;2.作为参数解析器,例如对RequestBody标识的参数进行解析 判断是否支持当前类型的参数 Overrid…...
函数的极限
目录 函数的极限 函数极限的定义: 例题: 左右极限: 自变量趋于无穷大时函数的极限: 例题: 函数极限的性质: 函数极限与数列极限之间的关系: 函数的极限 函数极限的定义: 一句…...
dnf命令使用
1. 简介 DNF是新一代的rpm软件包管理器。他首先出现在 Fedora 18 这个发行版中。而最近,它取代了yum,正式成为 Fedora 22 的包管理器 DNF包管理器克服了YUM包管理器的一些瓶颈,提升了包括用户体验,内存占用,依赖分析…...
CLIP CLAP
文章目录CLIPabstractintroCLAP: LEARNING AUDIO CONCEPTS FROM NATURAL LANGUAGE SUPERVISIONabstractmethodCLIP open AI2021.2代码&预训练模型 abstract 原有的基于有监督数据训练的计算机分类任务,在面对新的分类目标时泛化性和可用性都会变差࿱…...
Debezium报错处理系列之五十二:解决Sql Server数据库安装后修改主机名导致sqlserver数据库实例名称没有修改从而无法设置CDC的问题
Debezium报错处理系列之五十二:解决Sql Server数据库安装后修改主机名导致sqlserver数据库实例名称没有修改从而无法设置CDC的问题 一、完整报错二、错误原因三、解决方法Debezium报错处理系列一:The db history topic is missing. Debezium报错处理系列二:Make sure that t…...
scratch老鹰捉小鸡 电子学会图形化编程scratch等级考试二级真题和答案解析2022年12月
目录 scratch老鹰捉小鸡 一、题目要求 1、准备工作 2、功能实现 二、案例分析 <...
概率论小课堂:公理化过程(大数据方法解决问题的理论基础)
文章目录 引言I 初等概率论1.1 19世纪概率论的最大难题1.2 伯努利版本的大数定理1.3 切比雪夫版本的大数定理II 现代概率论(用公理来描述概率论)2.1 柯尔莫哥洛夫2.1 用公理来描述概率论III 最基本的概率论定理3.1 互补事件的概率之和等于13.2 不可能事件的概率为零引言 前苏…...
WOW64 IsWow64Process GetNativeSystemInfoWindows System32 SysWOW64
最近开发有遇到这方面的一些知识点,在此记录下。首先,什么是WOW64?在知道这个之前我觉得需要了解一下,C:\\Windows\\System32和C:\\Winodws\\SysWOW64这两个文件夹的区别,Windows系统最开始的时候出的就是32bit的系统&…...
Spring Boot 3.0系列【10】核心特性篇之应用配置的高阶用法
有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot版本3.0.3 源码地址:https://gitee.com/pearl-organization/study-spring-boot3 文章目录 前言1. 命令行2. JSON3. 外部化配置3.1 配置文件加载位置3.2 导入配置3.2 属性占位符4. 加密配置5. 加载YML配置文件6. 配…...
Java int类型数值比较总结
如果是int类型,判断相等的话直接使用 ""来判断,例如: int i 10; int j 10; System.out.print(i j); 如果是Integer类型,则可以使用equals方法进行相等比较。 int与Integer的基本使用对比 (…...
Pyspark基础入门5_RDD的持久化方法
Pyspark 注:大家觉得博客好的话,别忘了点赞收藏呀,本人每周都会更新关于人工智能和大数据相关的内容,内容多为原创,Python Java Scala SQL 代码,CV NLP 推荐系统等,Spark Flink Kafka Hbase Hi…...
汽车娱乐系统解决方案
Danlaw在汽车和航空航天行业里是全球知名的技术和服务供应商,致力于提供更加安全与智能的系统。Danlaw以突破性技术和高效开发、动态环境的自适应解决方案而闻名。Danlaw优秀的联网汽车解决方案使之成为全球大型互联设备供应商之一。 一 信息娱乐系统测试 | 风丘科…...
Go语言结构体,这一篇就够了
Go语言结构体,这一篇就够了1.结构体的概念2.结构体的定义3.结构体的实例化4.结构体初始化5.构造函数6.方法和接收者方法接收者7.嵌套结构体8.结构体的“继承”9.结构体与JSON序列化10.结构体标签(Tag)Go语言中没有“类”的概念,也…...
从码农到冥府CTO:重建六道轮回系统的质量保障实践
第一章 职业跃迁:技术人的冥府晋升之路1.1 技术职级体系重构冥府技术团队沿用硅谷职级模型,但增设业力评估维度:L1 鬼卒程序员:执行生死簿数据录入(日均处理10万条因果记录)L3 无常高级工程师:负…...
基于Python的宽带业务管理系统毕设源码
博主介绍:✌ 专注于Java,python,✌关注✌私信我✌具体的问题,我会尽力帮助你。一、研究目的本研究旨在设计并实现一个基于Python的宽带业务管理系统,以提升宽带服务提供商的业务管理效率和客户服务质量。具体研究目的如下:系统架构…...
Kook Zimage真实幻想Turbo部署案例:Jetson AGX Orin边缘设备轻量化幻想图推理尝试
Kook Zimage真实幻想Turbo部署案例:Jetson AGX Orin边缘设备轻量化幻想图推理尝试 1. 为什么在Jetson上跑幻想图?——不是“能不能”,而是“值不值” 很多人看到“幻想风格文生图”第一反应是:这得A100起步吧?显存不…...
实战:在无商店的Win10企业版ThinkPad上,通过PowerShell手动部署Lenovo Vantage
1. 为什么需要手动部署Lenovo Vantage 很多ThinkPad用户可能都遇到过这样的困扰:新装的Windows 10企业版系统找不到微软应用商店,而Lenovo Vantage这个必备的管理工具又只能通过商店安装。作为一个长期使用ThinkPad的技术博主,我完全理解这种…...
在VSCode中高效使用cl.exe构建和调试活动文件的AI辅助开发实践
在Windows平台上进行C开发,cl.exe是绕不开的核心编译器。很多朋友习惯在VSCode中写代码,但调试时却不得不先打开那个黑底的“Developer Command Prompt for VS”,再在里面启动VSCode,否则就会遇到找不到cl.exe或者链接库失败的经典…...
达摩院智能客服人工智能训练师实战:从模型训练到生产部署的全链路优化
在智能客服系统的开发过程中,我们常常面临一个核心矛盾:业务方希望模型能快速迭代、精准理解用户意图,而技术团队则受困于漫长的训练周期、复杂的多轮对话逻辑以及繁琐的生产部署流程。传统的自建训练环境,从数据清洗、特征工程到…...
3大核心能力实现高效水印移除:WatermarkRemover-AI全解析
3大核心能力实现高效水印移除:WatermarkRemover-AI全解析 【免费下载链接】WatermarkRemover-AI AI-Powered Watermark Remover using Florence-2 and LaMA Models: A Python application leveraging state-of-the-art deep learning models to effectively remove …...
phpIPAM vs Netbox深度对比:开源IP管理工具选型指南(附GCP云环境部署实录)
phpIPAM vs Netbox深度对比:开源IP管理工具选型指南(附GCP云环境部署实录) 在数字化转型浪潮中,企业网络基础设施的复杂度呈指数级增长。IP地址作为网络通信的基础要素,其管理效率直接影响运维团队的工作效能。传统Exc…...
教培人必看!那些好用到哭的网课平台大盘点
一、引言:网课平台,教培行业的新战场 在互联网浪潮的席卷下,教培行业正经历着前所未有的变革。曾经,学生们只能在固定的时间和地点,坐在教室里听老师授课。而如今,随着网课平台的兴起,学习的时…...
DAMA数据资产目录实战:从零搭建企业级数据管理系统的5个关键步骤
DAMA数据资产目录实战:从零搭建企业级数据管理系统的5个关键步骤 当企业数据量呈指数级增长时,最令人头疼的往往不是存储问题,而是"数据在哪?谁能用?怎么用?"这三个灵魂拷问。去年我们为一家中型…...
