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

( “树” 之 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^4104<=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. 平衡二叉树 给定一个二叉树&#xff0c;判断它是否是高度平衡的二叉树。 本题中&#xff0c;一棵高度平衡二叉树定义为&#xff1a; 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] …...

nvm软件使用-同一个环境下控制多个不同node版本

1.使用场景 nvm是一个用于管理Node.js版本的工具&#xff0c;它可以让你在同一台机器上安装和切换不同的Node.js版本。使用nvm的好处有以下几点&#xff1a; 1.1.nvm可以让你轻松地测试你的代码在不同的Node.js版本下的兼容性和性能&#xff0c;避免因为版本差异导致的问题。…...

连续两个南航的研究生面试出了从来没出现过的问题,本科和研究生都是计算机专业的,竟然说static是不可更改的。

最近面试人数有点多&#xff0c;面试有点频繁&#xff0c;因此发现了一些学生普遍会发生的错误&#xff0c;可以说是很离谱。 因为做了十多年的面试官&#xff0c;无论是大中小厂的面试&#xff0c;还是社招、校招。 从来没有遇到过这样的情况&#xff0c;而且发生在两个南航…...

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为例来介绍&#xff0c;解压后我们…...

Rust社区引发舆论危机,问题到底出在哪儿?

围绕开源的法律问题&#xff0c;讨论焦点往往集中在开源许可证、软件著作权等方面&#xff0c;商标的讨论却极少引人关注。事实上&#xff0c;关于开源软件以及开源软件的衍生产品的商标使用情况往往处于某种灰色地带。 最近&#xff0c;Rust基金会正在就更新的商标政策征求反馈…...

C++算法恢复训练之归并排序

归并排序&#xff08;Merge Sort&#xff09;是一种基于分治思想的排序算法&#xff0c;它将待排序数组分成两个子数组&#xff0c;然后对这两个子数组分别进行排序&#xff0c;最后将两个已排序的子数组合并成一个有序数组。归并排序是一种稳定的排序算法&#xff0c;具体体现…...

使用Process Explorer和Clumsy工具定位软件高CPU占用问题

目录 1、问题描述 2、使用Process Explorer初步找到CPU占用高的原因 3、使用Clumsy工具在公司内网环境复现了问题...

为何巴菲特和马斯克站在了一起?

股神巴菲特虽然非常传奇&#xff0c;但是马斯克对其并不感冒。马斯克曾经在一档电视节目中表示&#xff0c;实业才是王道&#xff0c;埋怨金融业抢走太多人才和精英&#xff0c;暗指巴菲特为年轻人做了错误示范。当然&#xff0c;巴菲特的投资非常厉害&#xff0c;但也有失手的…...

企业数字化转型全是坑?这几篇数字化转型成功案例,减少70%损失

这篇给大家整理了200企业数字化转型案例合集&#xff0c;涵盖了制造、建筑、教育、零售、互联网等10行业的大中小型企业数字化转型思路&#xff0c;希望对大家有所帮助。 案例全部整合在这篇文章中&#xff0c;点击即可查看>>数字化干货资料合集&#xff01; 01 首先&…...

13.Java面向对象----嵌套类

Java面向对象—嵌套类、内部类、匿名类 一、static静态 在《Java编程思想》有这样一段话&#xff1a;   “static方法就是没有this的方法。在static方法内部不能调用非静态方法&#xff0c;反过来是可以的。而且可以在没有创建任何对象的前提下&#xff0c;仅仅通过类本身来…...

Redis数据迁移过程,使用jedis客户端发送命令,需要注意string和byte类型的命令,如果使用的转换字符编码不一致,会导致丢数据

1.了解String与byte之间存在的字符编码映射规则&#xff08;java为例&#xff09; string与byte来回转换&#xff0c;需要指定一样字符编码规则 详细原因请参考&#xff1a;关于Java中bytes到String的转换-阿里云开发者社区 简单来说 &#xff08;1&#xff09;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压测&#xff08;固定事务数量&#xff09;TPC-C压测&#xff08;固定时长&#xff09;生成测试…...

Dapr和Rainbond集成,实现云原生BaaS和模块化微服务开发

背景 Dapr 是一个开源的分布式应用运行时&#xff0c;帮助开发者构建松耦合的分布式应用程序&#xff0c;具有良好的可扩展性和可维护性。Rainbond 是一款企业级的云原生应用管理平台&#xff0c;提供了丰富的功能和工具&#xff0c;方便开发者管理和部署应用。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&#xff08;Object Oriented&#xff09;&#xff0c;20 世纪 80 年代以后&#xff0c;有了面向对象分析&#xff08;OOA&#xff09;、 面向对象设计&#xff08;OOD&#xff09;、面向对象程序设计&#xff08;OOP&#xff09;等新的系统…...

【react 全家桶】组合组件

本人大二学生一枚&#xff0c;热爱前端&#xff0c;欢迎来交流学习哦&#xff0c;一起来学习吧。 <专栏推荐> &#x1f525;&#xff1a;js专栏 &#x1f525;&#xff1a;vue专栏 &#x1f525;&#xff1a;react专栏 文章目录09 【组合组件】1.包含关系2.特例关系问题…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...

大数据驱动企业决策智能化的路径与实践

&#x1f4dd;个人主页&#x1f339;&#xff1a;慌ZHANG-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、引言&#xff1a;数据驱动的企业竞争力重构 在这个瞬息万变的商业时代&#xff0c;“快者胜”的竞争逻辑愈发明显。企业如何在复杂环…...

VSCode 没有添加Windows右键菜单

关键字&#xff1a;VSCode&#xff1b;Windows右键菜单&#xff1b;注册表。 文章目录 前言一、工程环境二、配置流程1.右键文件打开2.右键文件夹打开3.右键空白处打开文件夹 三、测试总结 前言 安装 VSCode 时没有注意&#xff0c;实际使用的时候发现 VSCode 在 Windows 菜单栏…...

本地部署drawDB结合内网穿透技术实现数据库远程管控方案

文章目录 前言1. Windows本地部署DrawDB2. 安装Cpolar内网穿透3. 实现公网访问DrawDB4. 固定DrawDB公网地址 前言 在数字化浪潮席卷全球的背景下&#xff0c;数据治理能力正日益成为构建现代企业核心竞争力的关键因素。无论是全球500强企业的数据中枢系统&#xff0c;还是初创…...

npm install 相关命令

npm install 相关命令 基本安装命令 # 安装 package.json 中列出的所有依赖 npm install npm i # 简写形式# 安装特定包 npm install <package-name># 安装特定版本 npm install <package-name><version>依赖类型选项 # 安装为生产依赖&#xff08;默认&…...

【JavaEE】万字详解HTTP协议

HTTP是什么&#xff1f;-----互联网的“快递小哥” 想象我们正在网上购物&#xff1a;打开淘宝APP&#xff0c;搜索“蓝牙耳机”&#xff0c;点击商品图片&#xff0c;然后下单付款。这一系列操作背后&#xff0c;其实有一个看不见的“快递小哥”在帮我们传递信息&#xff0c;…...