T38,数的递归
描述
输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
样例解释:
样例二叉树如图,为一颗平衡二叉树
注:我们约定空树是平衡二叉树。
数据范围:n≤100n≤100,树上节点的val值满足 0≤n≤10000≤n≤1000
要求:空间复杂度O(1)O(1),时间复杂度 O(n)O(n)
输入描述:
输入一棵二叉树的根节点
返回值描述:
输出一个布尔类型的值
示例1
输入:
{1,2,3,4,5,6,7}
返回值:
true
示例2
输入:
{}
返回值:
true
递归实现:
public class Solution {public int deep(TreeNode root){if(root==null){return 0;}int left=deep(root.left);int right=deep(root.right);if(left>right){return left+1;}else{return right+1;}}public boolean IsBalanced_Solution(TreeNode root) {if(root==null){return true;}int left=deep(root.left);int right=deep(root.right);if(left-right>1||right-left>1){return false;}return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);}
}
思路:
一个求左右子树深度的方法deep,deep方法可递归调用deep方法,再次调用的参数为传入节点的左右子树,最后返回左右节点的值。结束标志是左右子树为空,返回0;
从根节点开始,调用deep方法,判断左右子树深度之差。递归调用该方法,参数为左右子树节点。结束标志是左右子树为0;
自底向上:
实现代码:
public class Solution {public boolean IsBalanced_Solution(TreeNode root) {//空树也是平衡二叉树if(root == null)return true;return getdepth(root) != -1;}public int getdepth(TreeNode root) {if(root == null)return 0;//递归计算当前root左右子树的深度差int left = getdepth(root.left);//当前节点左子树不平衡,则该树不平衡if(left < 0) return -1;int right = getdepth(root.right);//当前节点右子树不平衡,则该树不平衡if(right < 0) return -1;//计算深度差return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);}
}
时间复杂度:O(N)
空间复杂度:O(N)
附录:Math函数的方法Math的几个方法Math.round()、Math.ceil()、Math.floor()和Math.abs()记录一下_MingFlying的博客-CSDN博客
相关文章:

T38,数的递归
描述 输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。 在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树 平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空…...
QT+ OpenGL 变换
文章目录QT OpenGL变换向量的运算矩阵矩阵与向量相乘代码实现QT OpenGL 本篇完整工程见gitee:QTOpenGL 对应点的tag,由turbolove提供技术支持,您可以关注博主或者私信博主。 变换 我们需要改变物体的位置 现有解决办法(每一帧,…...

【算法】前缀和
作者:指针不指南吗 专栏:算法篇 🐾要学会在纸上打草稿,这个很重要🐾 文章目录1.什么是前缀和?2.怎么求前缀和?3.前缀和有什么用?4.进阶二维:矩阵和前缀和 主打一个记公式 1.什么是前…...

《Redis实战篇》七、Redis消息队列
7.1 Redis消息队列-认识消息队列 什么是消息队列:字面意思就是存放消息的队列。最简单的消息队列模型包括3个角色: 消息队列:存储和管理消息,也被称为消息代理(Message Broker)生产者:发送消息…...

android组件化
学习流程:1.开源最佳实践:Android平台页面路由框架ARouter-阿里云开发者社区 (aliyun.com)2.中文ARouter使用API:https://github.com/alibaba/ARouter/blob/master/README_CN.md3.看当前文档后面的代码4.这是通俗易懂的文章:https…...
华为OD机试真题Python实现【特异性双端队列】真题+解题思路+代码(20222023)
🔥系列专栏 华为OD机试(Python)真题目录汇总华为OD机试(JAVA)真题目录汇总华为OD机试(C++)真题目录汇总华为OD机试(JavaScript)真题目录汇总文章目录 🔥系列专栏题目输入输出示例一输入输出解题思路核心知识点Python 代码实现代码运行结果版权说明<...
24.架构能力
文章目录24. 架构能力24.1 Competence of Individuals: Duties, Skills, and Knowledge of Architects 个人能力:架构师的职责、技能和知识24.2 Competence of a Software Architecture Organization 软件架构组织的能力24.3 Summary 小结24.4 For Further Reading …...

前端原生 CSS 跑马灯效果,无限轮播(横竖版本,带渐变遮罩,简单实用)
一、横版跑马灯 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-wid…...

4.8 注解与自定义注解
文章目录1.概述2.注解的分类2.1 JDK注解2.2 元注解2.2.1 Target ElementType…2.2.2 Retention RetentionPolicy…3 自定义注解1.概述 在注解刚出现时,曾受到过好多程序员的鄙夷,觉得这就是多此一举的操作; 但随着时间的推移,越…...

webpack 的热更新是如何做到的?原理是什么?
Hot Module Replacement,简称 HMR,在不需要刷新整个页面的同时更新模块,能够提升开发的效率和体验。热更新时只会局部刷新页面上发生了变化的模块,同时可以保留当前页面的状态,比如复选框的选中状态等。 在 webpack 中…...

嵌入式ARM设计编程(一) 简单数据搬移
文章和代码已归档至【Github仓库:hardware-tutorial】,需要的朋友们自取。或者公众号【AIShareLab】回复 嵌入式 也可获取。 一、实验目的 熟悉实验开发环境,掌握简单ARM汇编指令的使用方法。 二、实验环境 硬件:PC机 软件&am…...

【Selenium】十分钟手把手带你学会WebDriver API
目录 1、定位元素【8种】 2、操作测试对象 3、添加等待 4、弹窗类型 5、浏览器的操作 6、键盘事件 7、选择框 8、上传文件 1、定位元素【8种】 元素定位是自动化测试的核心,想要去操作一个对象,第一步就是需要我们先去识别这个对象。每个对象就会…...

3DMAX高级弯曲插件使用教程
3dMax高级弯曲插件是对3dmax原生“弯曲(Bend)”修改器的一个增强,给用户更多控制弯曲修改器的参数设置,它让用户输入宽度,插件脚本将移动中心以获得正确的宽度。 主要特性: - 使用智能捕捉捕捉到自定义网格…...
前端面试题之性能优化大杂烩
主要内容为下面几大类:移动端、图片、JavaScript、css、html、页面内容、服务器、cookie。 移动端性能优化: 保持单个文件小于25KB 移动网站页面要求下载资源,如果文件过大,会大大减慢页面加载速度。 打包内容为分段multipart文…...

SpringBoot+Vue实现养老智慧服务平台
文末获取源码 开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7/8.0 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包:Maven3.3.9 浏…...
tigervnc2023
sudo apt-get install tigervnc-standalone-server 配置用户 /etc/tigervnc/vncserver.users :1user1 :2user2 :3user3 全局配置 /etc/tigervnc/vncserver-config-defaults $localhost"no"; $geometry "1920x1200"; 分别进入user1 user2 user3 用户…...

智能三子棋(人机大战)—— 你会是最终赢家吗?万字讲解让你实现与自己对弈
魔王的介绍:😶🌫️一名双非本科大一小白。魔王的目标:🤯努力赶上周围卷王的脚步。魔王的主页:🔥🔥🔥大魔王.🔥🔥🔥 ❤️…...

【自制开发板】自制STM32F407开发板(含TFT 8080串口屏幕接口)
【2023 年 2 月 14 日】 许久没有更新,最近做了个小开发板玩了玩。更新一下吧,作为记录!! 主要是象试一下LVGL在STM32上的应用,所以开发板的大小都是基于屏幕大小来设计的。 分享出来,给大家一个板子结构…...

openvino yolov5/ssd 实时推流目标检测在html上显示
安装ffmepg并添加到环境变量中,流媒体使用m7s 运行效果 SSD:检测在10ms左右,yolov5在100ms左右 app.py #!/usr/local/bin/python3 # encodin: utf-8import subprocess import threading import time import cv2 import osfrom OpenVinoYoloV…...

基于FPGA的 SPI通信 设计(1)
引言 低速通信目前搞过 UART串口通信、IIC通信。其实 SPI 也算是中低速(有时也可以用作高速通信)串行通信的范畴,但是一直还没真正实现过,所以此系列就 SPI的协议以及FPGA设计作几篇博客记录。欢迎订阅关注~ SPI 标准协议 x1模式…...

华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...

深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...