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

剑指 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. 平衡二叉树 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 输入一棵二叉树的根节点&#xff0c;判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1&#xff0c;那么它就是一棵平衡二叉树。 示例 1: 给定二叉树 […...

一文吃透前端低代码的 “神仙生活”

今天来说说前端低代码有多幸福&#xff1f; 低代码是啥&#xff1f;顾名思义少写代码…… 这种情况下带来的幸福有&#xff1a;代码写得少&#xff0c;bug也就越少&#xff08;所谓“少做少错”&#xff09;&#xff0c;因此开发环节的两大支柱性工作“赶需求”和“修bug”就…...

【深度学习】预训练语言模型-BERT

1.BERT简介 BERT是一种预训练语言模型&#xff08;pre-trained language model, PLM&#xff09;&#xff0c;其全称是Bidirectional Encoder Representations from Transformers。下面从语言模型和预训练开始展开对预训练语言模型BERT的介绍。 1-1 语言模型 语言模型 &#xf…...

C++类的组合

C类的组合什么是类的组合初始化参数列表使用类的组合案例分析组合构造和析构顺序问题this指针基本用法和作用什么是类的组合 类的组合就是以另一个对象为数据成员&#xff0c;这种情况称为类的组合 1.优先使用类的组合&#xff0c;而不是继承 2.组合表达式的含义 一部分关系 初…...

2.伪随机数生成器(ctr_drbg)的配置与使用

零、随机数应用 生成盐,用于基于口令的密码 生成密钥,用于加密和认证 生成一次性整数Nonce,防止重放攻击 生成初始化向量IV 构成 种子,真随机数生成器的种子来源于物理现象 内部状态,种子用来初始化内部状态 一、真随机数和伪随机数 1.区别 随机数在安全技术中通常被用于…...

CentOS7 切换图形模式和多用户命令行模式

备注&#xff1a; 主机名 hw 含义&#xff1a;hardware 缩写&#xff0c;意思是硬件&#xff08;物理机&#xff09; 文章目录1、查看源头2、查看当前系统运行模式3、设置系统运行模式为多用户命令行模式4、查看当前系统运行模式5、重启系统6、确认当前系统运行模式7、设置系统…...

在linux上用SDKMan对Java进行多版本管理

在linux上用SDKMan对Java进行多版本管理 有一个工具叫SDKMan&#xff0c;它允许我们这样做。官方网站这样描述: TIP: "SDKMan 是一个工具&#xff0c;用于在大多数基于Unix的系统上管理多个软件开发工具包的并行版本。它提供了一个方便的命令行接口(CLI)和API&#xff0c…...

JSONObject、fastJson(JsonObject)、Gson(JsonObject)区别

概述 Java中并没有内置的 JSON 解析&#xff0c;需要使用第三方类库 fastJson &#xff1a;阿里巴巴的JSON 库&#xff0c;优势在于解析速度快&#xff0c;解析效率高&#xff0c;可以轻松处理大量的 JSON 数据JackSon &#xff1a; 社区十分活跃&#xff0c;spring框架默认使…...

如何在CSDN中使用ChatGPT

本篇文章致力于帮助大家理解和使用ChatGPT&#xff08;现在CSDN改成”C知道“了&#xff09;。简介ChatGPT是OpenAI公司开发的一种大型语言模型。它是一种基于Transformer架构的深度学习模型&#xff0c;可以对语言进行建模和生成。它可以处理问答、对话生成、文本生成等多种任…...

【Spring6】| GoF之工厂模式

目录 一&#xff1a;GoF之工厂模式 1. 工厂模式的三种形态 2. 简单工厂模式 3. 工厂方法模式 4. 抽象工厂模式&#xff08;了解&#xff09; 一&#xff1a;GoF之工厂模式 &#xff08;1&#xff09;GoF&#xff08;Gang of Four&#xff09;&#xff0c;中文名——四人组…...

初识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;//引脚位置&#xff0c;根据原理图可知 sbit key1 P2^1; sbit key2 P2^0; void …...

redis数据持久化

redis备份概念 Redis所有数据都是保存在内存中&#xff0c;Redis数据备份可以定期的通过异步方式保存到磁盘上&#xff0c;该方式称为半持久化模式&#xff0c;如果每一次数据变化都写入aof文件里面&#xff0c;则称为全持久化模式。同时还可以基于Redis主从复制实现Redis备份…...

Java StringBuffer类

Java StringBuffer类是Java语言中一个非常重要的类&#xff0c;它提供了丰富的方法&#xff0c;可以方便地进行字符串操作。本文将详细介绍Java StringBuffer类的作用以及在实际工作中的用途。 StringBuffer类的作用 Java StringBuffer类是一个可变的字符串缓冲区&#xff0c…...

电路模型和电路定律(2)——“电路分析”

各位CSDN的uu们你们好呀&#xff0c;好久没有更新电路分析的文章啦&#xff0c;今天来小小复习一波&#xff0c;之前那篇博客&#xff0c;小雅兰更新了电路的历史以及电压电流的参考方向&#xff0c;这篇博客小雅兰继续&#xff01;&#xff01;&#xff01; 电阻元件 电压源和…...

天琊超级进程监视器的应用试验(19)

实验目的 1、了解进程概念及其基本原理&#xff1b; 2、掌握天琊超级进程监视器的安装与使用。预备知识 本实验要求实验者具备如下的相关知识。 操作系统的安全配置是整个系统安全审计策略核心&#xff0c;其目的就是从系统根源构筑安全防护体系&#xff0c;通过用户的一…...

使用 Pulumi 打造自己的多云管理平台

前言在公有云技术与产品飞速发展的时代&#xff0c;业务对于其自身的可用性提出了越来越高的要求&#xff0c;当跨区域容灾已经无法满足业务需求的情况下&#xff0c;我们通常会考虑多云部署我们的业务平台&#xff0c;以规避更大规模的风险。但在多云平台部署的架构下&#xf…...

什么是MyBatis?无论是基础教学还是技术精进,你都应该看这篇MyBatis

文章目录学习之前&#xff0c;跟你们说点事情&#xff0c;有助于你能快速看完文章一、先应用再学习&#xff0c;代码示例1. 第一个MyBatis程序2. MyBatis整合Spring3. SpringBoot整合MyBatis二、MyBatis整体流程&#xff0c;各组件的作用域和生命周期三、说说MyBatis-config.xm…...

【编程基础之Python】10、Python中的运算符

【编程基础之Python】10、Python中的运算符Python中的运算符算术运算符赋值运算符比较运算符逻辑运算符位运算符成员运算符身份运算符运算符优先级运算符总结Python中的运算符 Python是一门非常流行的编程语言&#xff0c;它支持各种运算符来执行各种操作。这篇文章将详细介绍…...

Android的基础介绍

一、Android介绍 Android是一种基于Linux的自由及开放源代码的操作系统,Android 分为四个层,从高层到低层分别是应用程序层、应用程序框架层、系统运行库层和Linux内核层。 Android 是Google开发的基于Linux平台的开源手机操作系统。它包括操作系统、用户界面和应用程序——…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...