( “树” 之 DFS) 110. 平衡二叉树 ——【Leetcode每日一题】
110. 平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:true
示例 2:

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false
示例 3:
输入:root = []
输出:true
提示:
- 树中的节点数在范围 [0, 5000] 内
- −104<=Node.val<=104-10^4 <= Node.val <= 10^4−104<=Node.val<=104
思路:自底向上的递归
自底向上递归的做法类似于后序遍历:
- 对于当前遍历到的节点,先递归地判断其左右子树是否平衡;
- 再判断以当前节点为根的子树是否平衡。如果存在一棵子树不平衡,则整个二叉树一定不平衡, 则返回。
- 如果一棵子树是平衡的,则返回其高度(取左右子树最大值);
代码:(Java、C++)
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 {private boolean result = true;public boolean isBalanced(TreeNode root) {height(root);return result;}public int height(TreeNode root){if(root == null) return 0;int left = height(root.left);int right = height(root.right);if(Math.abs(left - right) > 1){result = false;return 0;}return 1 + Math.max(left, right);}
}
C++
/*** 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:bool result = true;bool isBalanced(TreeNode* root) {height(root);return result;}int height(TreeNode* root){if(root == NULL) return 0;int left = height(root->left);int right = height(root->right);if(abs(left - right) > 1){result = false;return 0;}return 1 + max(left, right);}
};
运行结果:

复杂度分析:
-
时间复杂度:O(n)O(n)O(n),其中
n是二叉树中的节点个数。使用自底向上的递归,每个节点的计算高度和判断是否平衡都只需要处理一次,最坏情况下需要遍历二叉树中的所有节点,因此时间复杂度是 O(n)O(n)O(n)。 -
空间复杂度:O(n)O(n)O(n),其中
n是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数,递归调用的层数不会超过n。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:
( “树” 之 DFS) 110. 平衡二叉树 ——【Leetcode每日一题】
110. 平衡二叉树 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1: 输入:root [3,9,20,null,null,15,7] …...
nvm软件使用-同一个环境下控制多个不同node版本
1.使用场景 nvm是一个用于管理Node.js版本的工具,它可以让你在同一台机器上安装和切换不同的Node.js版本。使用nvm的好处有以下几点: 1.1.nvm可以让你轻松地测试你的代码在不同的Node.js版本下的兼容性和性能,避免因为版本差异导致的问题。…...
连续两个南航的研究生面试出了从来没出现过的问题,本科和研究生都是计算机专业的,竟然说static是不可更改的。
最近面试人数有点多,面试有点频繁,因此发现了一些学生普遍会发生的错误,可以说是很离谱。 因为做了十多年的面试官,无论是大中小厂的面试,还是社招、校招。 从来没有遇到过这样的情况,而且发生在两个南航…...
How to install nacos/nacos-server:v2.1.2-slim with docker
今天给大家介绍一下如何基于Docker的nacos/nacos-server:v2.1.2-slim镜像安装nacos 1、Data Source 我们需要从nacos的github官网下载nacos 2.12发布包 nacos-server-2.1.2.tar.gznacos-server-2.1.2.zip 这里以nacos-server-2.1.2.tar.gz为例来介绍,解压后我们…...
Rust社区引发舆论危机,问题到底出在哪儿?
围绕开源的法律问题,讨论焦点往往集中在开源许可证、软件著作权等方面,商标的讨论却极少引人关注。事实上,关于开源软件以及开源软件的衍生产品的商标使用情况往往处于某种灰色地带。 最近,Rust基金会正在就更新的商标政策征求反馈…...
C++算法恢复训练之归并排序
归并排序(Merge Sort)是一种基于分治思想的排序算法,它将待排序数组分成两个子数组,然后对这两个子数组分别进行排序,最后将两个已排序的子数组合并成一个有序数组。归并排序是一种稳定的排序算法,具体体现…...
使用Process Explorer和Clumsy工具定位软件高CPU占用问题
目录 1、问题描述 2、使用Process Explorer初步找到CPU占用高的原因 3、使用Clumsy工具在公司内网环境复现了问题...
为何巴菲特和马斯克站在了一起?
股神巴菲特虽然非常传奇,但是马斯克对其并不感冒。马斯克曾经在一档电视节目中表示,实业才是王道,埋怨金融业抢走太多人才和精英,暗指巴菲特为年轻人做了错误示范。当然,巴菲特的投资非常厉害,但也有失手的…...
企业数字化转型全是坑?这几篇数字化转型成功案例,减少70%损失
这篇给大家整理了200企业数字化转型案例合集,涵盖了制造、建筑、教育、零售、互联网等10行业的大中小型企业数字化转型思路,希望对大家有所帮助。 案例全部整合在这篇文章中,点击即可查看>>数字化干货资料合集! 01 首先&…...
13.Java面向对象----嵌套类
Java面向对象—嵌套类、内部类、匿名类 一、static静态 在《Java编程思想》有这样一段话: “static方法就是没有this的方法。在static方法内部不能调用非静态方法,反过来是可以的。而且可以在没有创建任何对象的前提下,仅仅通过类本身来…...
Redis数据迁移过程,使用jedis客户端发送命令,需要注意string和byte类型的命令,如果使用的转换字符编码不一致,会导致丢数据
1.了解String与byte之间存在的字符编码映射规则(java为例) string与byte来回转换,需要指定一样字符编码规则 详细原因请参考:关于Java中bytes到String的转换-阿里云开发者社区 简单来说 (1)string和by…...
第六章 IA-32指令类型
IA-32指令类型1、传送指令1.1、常用传送指令1.1.1、通用数据传送指令1.2、传送指令执行过程2、定点算术运算指令2.1、常用定点运算指令2.2、加法运算的底层实现举例2.3、加法指令和乘法指令举例3、按位运算指令3.1、逻辑运算和移位运算3.2、按位运算指令举例4、控制转移指令4.1…...
基于BenchmarkSQL的Oracle数据库tpcc性能测试
基于BenchmarkSQL的Oracle数据库tpcc性能测试安装BenchmarkSQL及其依赖安装软件依赖编译BenchmarkSQLBenchmarkSQL props文件配置数据库用户配置BenchmarkSQL压测装载测试数据TPC-C压测(固定事务数量)TPC-C压测(固定时长)生成测试…...
Dapr和Rainbond集成,实现云原生BaaS和模块化微服务开发
背景 Dapr 是一个开源的分布式应用运行时,帮助开发者构建松耦合的分布式应用程序,具有良好的可扩展性和可维护性。Rainbond 是一款企业级的云原生应用管理平台,提供了丰富的功能和工具,方便开发者管理和部署应用。Rainbond 和 Da…...
全国青少年信息素养大赛2023年python·选做题模拟五卷
目录 下载打印文档做题: 全国青少年电子信息智能创新大赛 python选做题模拟五卷 一、单选题 1. 对于数列3,8,11,15,17,19,25,30,44,采用“二分查找”法查找8,需要查找多少次?( ) A、5...
itop-3568开发板驱动学习笔记(18)tasklet 机制
《【北京迅为】itop-3568开发板驱动开发指南.pdf》 学习笔记 文章目录tasklet 简介tasklet 结构体tasklet 初始化使能 tasklet失能 tasklettasklet 调度函数tasklet 取消调度函数tasklet 实验tasklet 简介 Tasklets 机制是linux中断处理机制中的软中断延迟机制。在linux中存在着…...
全国青少年电子信息智能创新大赛(复赛)python·模拟二卷
目录 编程题一 答案解析: 打印题目下载做题: 全国青少年电子信息智能创新大赛(复赛)python模拟二卷 编程题一 第一题:描述 输入两个整数,比较它们的大小。 输入 一行,包含两个整数x和y,中间用单个空格隔开。 0<= x<2^32,-2^31 <= y<2^31。 输出...
对标ChatGPT的开源中文方案
目录 前言 一、Meta发布大语言模型LLaMA 二、斯坦福基于 Meta 的 LLaMA 7B 模型微调出Alpaca 三、基于TencentPretrain训练中文LLaMA大规模语言模型 四、基于斯坦福Alpaca训练中文对话大模型BELLE 五、 清华开源项目ChatGLM中文对话模型 六、基于LLaMA的开源中文语言模型…...
9.Java面向对象----封装
Java面向对象—封装 面向对象简称 OO(Object Oriented),20 世纪 80 年代以后,有了面向对象分析(OOA)、 面向对象设计(OOD)、面向对象程序设计(OOP)等新的系统…...
【react 全家桶】组合组件
本人大二学生一枚,热爱前端,欢迎来交流学习哦,一起来学习吧。 <专栏推荐> 🔥:js专栏 🔥:vue专栏 🔥:react专栏 文章目录09 【组合组件】1.包含关系2.特例关系问题…...
从零到数据分析:用ClickHouse+DBeaver在Windows上复现一个电商用户行为查询
从零构建电商数据分析平台:Windows下ClickHouse与DBeaver实战指南 1. 为什么选择ClickHouse进行电商行为分析? 去年双十一期间,某头部电商平台通过实时分析用户点击流数据,在活动开始后30分钟内就调整了首页推荐策略,…...
Vitis新手避坑:自定义IP编译报错?先检查这个Makefile路径!
Vitis新手避坑指南:自定义IP编译报错的核心排查思路 第一次在Vitis中集成自定义IP时遇到编译报错,那种挫败感我至今记忆犹新。明明硬件描述文件(XSA)已经正确生成,软件工程却莫名其妙地报出"xxx.h: No such file …...
Qt项目里用dxflib解析CAD图纸,遇到带圆弧的多段线(LWPOLYLINE)怎么画?
Qt项目中利用dxflib解析CAD图纸:带圆弧多段线(LWPOLYLINE)的精确绘制方案 在工业设计、建筑图纸和机械制图领域,DXF文件作为CAD数据交换的标准格式,其精确解析一直是开发者的核心挑战。当使用Qt框架结合dxflib库进行CAD可视化时,优…...
Vision Transformers在密集预测任务中的创新应用与性能优化
1. Vision Transformers如何革新密集预测任务 第一次接触Vision Transformers(ViT)时,我完全被它的设计哲学震撼到了。传统的CNN在处理图像时,就像用固定大小的网格去观察世界,而ViT则像是一个拥有"全局视野"…...
策划和程序不再打架:Unity+Excel打造可视化游戏数据配置工作流
Unity与Excel深度整合:构建高效游戏数据配置系统 在中小型游戏开发团队中,策划与程序之间的数据流转往往是效率瓶颈所在。策划需要频繁调整数值平衡,而程序员则疲于应对无尽的配置表更新请求。这套基于UnityExcel的工作流解决方案,…...
不止于步骤:用SPM预处理fMRI数据时,那些没人告诉你的‘隐藏’技巧与效率工具
不止于步骤:用SPM预处理fMRI数据时,那些没人告诉你的‘隐藏’技巧与效率工具 当你面对上百个被试的fMRI数据时,是否曾为重复点击SPM的GUI界面而感到疲惫?是否担心手动操作带来的潜在错误?本文将带你超越基础教程&#…...
工业相机LUCID TRI050S偏振模式实战:从开箱到计算AOP/DOP的保姆级避坑指南
工业相机LUCID TRI050S偏振模式实战:从开箱到计算AOP/DOP的保姆级避坑指南 当你第一次拿到LUCID TRI050S这款工业级偏振相机时,可能会被它小巧的金属机身和复杂的接口配置所震撼。与普通工业相机不同,这款设备在每个像素点前都集成了微型偏振…...
罗斯蒙特RoseMount手操器TREXLFPKL9S1
罗斯蒙特475手操器是一款由艾默生(Emerson)推出的高性能现场通讯设备,广泛应用于工业自动化领域,用于配置、校准和诊断HART及Foundation Fieldbus协议的智能仪表设备。它具备彩色图形界面、蓝牙通信、强大的现场诊断功能和可用户升…...
从零到一:构建你的第一个智能体应用实战指南
1. 为什么你需要一个智能体应用? 想象一下这样的场景:每天早上你的手机自动整理当天的重要会议和待办事项,根据你的日程推荐最佳出行路线;工作时自动汇总行业动态和关键邮件;晚上回家前提前打开空调并推荐符合你口味的…...
Python离线环境搭建全攻略:从虚拟机到生产服务器的完整迁移方案
Python离线环境搭建全攻略:从虚拟机到生产服务器的完整迁移方案 在金融、军工等对网络安全要求极高的行业,服务器通常运行在完全隔离的离线环境中。这种环境下,如何部署Python运行环境并确保所有依赖库正常工作,成为许多运维工程师…...
