剑指 Offer 55 - II. 平衡二叉树
剑指 Offer 55 - II. 平衡二叉树
难度:easy\color{Green}{easy}easy
题目描述
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7][3,9,20,null,null,15,7][3,9,20,null,null,15,7]
3/ \9 20/ \15 7
返回 truetruetrue 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4][1,2,2,3,3,null,null,4,4][1,2,2,3,3,null,null,4,4]
1/ \2 2/ \3 3/ \4 4
返回 falsefalsefalse 。
限制:
- 0<=树的结点个数<=100000 <= 树的结点个数 <= 100000<=树的结点个数<=10000
注意:本题与主站 110 题相同:https://leetcode-cn.com/problems/balanced-binary-tree/
算法
(递归)
递归判断:
先递归判断两棵子树是否是平衡的,递归的过程中记录每棵树的最大深度值,然后判断两棵子树的最大深度的差是否不大于1。
复杂度分析
-
时间复杂度:每个节点仅被遍历一次,且判断的复杂度是 O(1)O(1)O(1)。所以总时间复杂度是O(n)O(n)O(n)。
-
空间复杂度 : O(n)O(n)O(n)
C++ 代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool ans;bool isBalanced(TreeNode* root) {ans = true;dfs(root);return ans;}int dfs(TreeNode* root) {if (!root) return 0;int lh = dfs(root->left), rh = dfs(root->right);if (abs(lh - rh) > 1) ans = false;return max(lh, rh) + 1;}
};
算法2
构造一个获取当前子树的深度的函数 maxdepth(root) ,通过比较某子树的左右子树的深度差 abs(maxdepth(root.left) - maxdepth(root.right)) <= 1 是否成立,来判断某子树是否是二叉平衡树。若所有子树都平衡,则此树平衡。
C++ 代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {if (!root) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}bool isBalanced(TreeNode* root) {if (!root) return true;int left = maxDepth(root->left);int right = maxDepth(root->right);return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);}
};
相关文章:
剑指 Offer 55 - II. 平衡二叉树
剑指 Offer 55 - II. 平衡二叉树 难度:easy\color{Green}{easy}easy 题目描述 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 示例 1: 给定二叉树 […...
一文吃透前端低代码的 “神仙生活”
今天来说说前端低代码有多幸福? 低代码是啥?顾名思义少写代码…… 这种情况下带来的幸福有:代码写得少,bug也就越少(所谓“少做少错”),因此开发环节的两大支柱性工作“赶需求”和“修bug”就…...
【深度学习】预训练语言模型-BERT
1.BERT简介 BERT是一种预训练语言模型(pre-trained language model, PLM),其全称是Bidirectional Encoder Representations from Transformers。下面从语言模型和预训练开始展开对预训练语言模型BERT的介绍。 1-1 语言模型 语言模型 …...
C++类的组合
C类的组合什么是类的组合初始化参数列表使用类的组合案例分析组合构造和析构顺序问题this指针基本用法和作用什么是类的组合 类的组合就是以另一个对象为数据成员,这种情况称为类的组合 1.优先使用类的组合,而不是继承 2.组合表达式的含义 一部分关系 初…...
2.伪随机数生成器(ctr_drbg)的配置与使用
零、随机数应用 生成盐,用于基于口令的密码 生成密钥,用于加密和认证 生成一次性整数Nonce,防止重放攻击 生成初始化向量IV 构成 种子,真随机数生成器的种子来源于物理现象 内部状态,种子用来初始化内部状态 一、真随机数和伪随机数 1.区别 随机数在安全技术中通常被用于…...
CentOS7 切换图形模式和多用户命令行模式
备注: 主机名 hw 含义:hardware 缩写,意思是硬件(物理机) 文章目录1、查看源头2、查看当前系统运行模式3、设置系统运行模式为多用户命令行模式4、查看当前系统运行模式5、重启系统6、确认当前系统运行模式7、设置系统…...
在linux上用SDKMan对Java进行多版本管理
在linux上用SDKMan对Java进行多版本管理 有一个工具叫SDKMan,它允许我们这样做。官方网站这样描述: TIP: "SDKMan 是一个工具,用于在大多数基于Unix的系统上管理多个软件开发工具包的并行版本。它提供了一个方便的命令行接口(CLI)和API,…...
JSONObject、fastJson(JsonObject)、Gson(JsonObject)区别
概述 Java中并没有内置的 JSON 解析,需要使用第三方类库 fastJson :阿里巴巴的JSON 库,优势在于解析速度快,解析效率高,可以轻松处理大量的 JSON 数据JackSon : 社区十分活跃,spring框架默认使…...
如何在CSDN中使用ChatGPT
本篇文章致力于帮助大家理解和使用ChatGPT(现在CSDN改成”C知道“了)。简介ChatGPT是OpenAI公司开发的一种大型语言模型。它是一种基于Transformer架构的深度学习模型,可以对语言进行建模和生成。它可以处理问答、对话生成、文本生成等多种任…...
【Spring6】| GoF之工厂模式
目录 一:GoF之工厂模式 1. 工厂模式的三种形态 2. 简单工厂模式 3. 工厂方法模式 4. 抽象工厂模式(了解) 一:GoF之工厂模式 (1)GoF(Gang of Four),中文名——四人组…...
初识Node.js
文章目录初识Node.jsNode.js简介fs模块演示路径问题path路径模块http模块创建web服务器得基本步骤req请求对象res响应对象解决中文乱码问题模块化的基本慨念1、模块化2、Node.js中模块的分类3、Node.js中的模块作用域3.1什么是模块作用域4、向外共享模块作用域中的成员4.1modul…...
C51---软件消抖
1.example #include "reg52.h" #include "intrins.h" //main.c(11): error C264: intrinsic _nop_: declaration/activation error,添加这个头文件就可了 sbit led1 P3^7;//引脚位置,根据原理图可知 sbit key1 P2^1; sbit key2 P2^0; void …...
redis数据持久化
redis备份概念 Redis所有数据都是保存在内存中,Redis数据备份可以定期的通过异步方式保存到磁盘上,该方式称为半持久化模式,如果每一次数据变化都写入aof文件里面,则称为全持久化模式。同时还可以基于Redis主从复制实现Redis备份…...
Java StringBuffer类
Java StringBuffer类是Java语言中一个非常重要的类,它提供了丰富的方法,可以方便地进行字符串操作。本文将详细介绍Java StringBuffer类的作用以及在实际工作中的用途。 StringBuffer类的作用 Java StringBuffer类是一个可变的字符串缓冲区,…...
电路模型和电路定律(2)——“电路分析”
各位CSDN的uu们你们好呀,好久没有更新电路分析的文章啦,今天来小小复习一波,之前那篇博客,小雅兰更新了电路的历史以及电压电流的参考方向,这篇博客小雅兰继续!!! 电阻元件 电压源和…...
天琊超级进程监视器的应用试验(19)
实验目的 1、了解进程概念及其基本原理; 2、掌握天琊超级进程监视器的安装与使用。预备知识 本实验要求实验者具备如下的相关知识。 操作系统的安全配置是整个系统安全审计策略核心,其目的就是从系统根源构筑安全防护体系,通过用户的一…...
使用 Pulumi 打造自己的多云管理平台
前言在公有云技术与产品飞速发展的时代,业务对于其自身的可用性提出了越来越高的要求,当跨区域容灾已经无法满足业务需求的情况下,我们通常会考虑多云部署我们的业务平台,以规避更大规模的风险。但在多云平台部署的架构下…...
什么是MyBatis?无论是基础教学还是技术精进,你都应该看这篇MyBatis
文章目录学习之前,跟你们说点事情,有助于你能快速看完文章一、先应用再学习,代码示例1. 第一个MyBatis程序2. MyBatis整合Spring3. SpringBoot整合MyBatis二、MyBatis整体流程,各组件的作用域和生命周期三、说说MyBatis-config.xm…...
【编程基础之Python】10、Python中的运算符
【编程基础之Python】10、Python中的运算符Python中的运算符算术运算符赋值运算符比较运算符逻辑运算符位运算符成员运算符身份运算符运算符优先级运算符总结Python中的运算符 Python是一门非常流行的编程语言,它支持各种运算符来执行各种操作。这篇文章将详细介绍…...
Android的基础介绍
一、Android介绍 Android是一种基于Linux的自由及开放源代码的操作系统,Android 分为四个层,从高层到低层分别是应用程序层、应用程序框架层、系统运行库层和Linux内核层。 Android 是Google开发的基于Linux平台的开源手机操作系统。它包括操作系统、用户界面和应用程序——…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
