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

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 二叉树&#xff0c;判断该二叉树是否是平衡二叉树。 在这里&#xff0c;我们只需要考虑其平衡性&#xff0c;不需要考虑其是不是排序二叉树 平衡二叉树&#xff08;Balanced Binary Tree&#xff09;&#xff0c;具有以下性质&#xff1a;它是一棵空…...

QT+ OpenGL 变换

文章目录QT OpenGL变换向量的运算矩阵矩阵与向量相乘代码实现QT OpenGL 本篇完整工程见gitee:QTOpenGL 对应点的tag&#xff0c;由turbolove提供技术支持&#xff0c;您可以关注博主或者私信博主。 变换 我们需要改变物体的位置 现有解决办法&#xff08;每一帧&#xff0c…...

【算法】前缀和

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

《Redis实战篇》七、Redis消息队列

7.1 Redis消息队列-认识消息队列 什么是消息队列&#xff1a;字面意思就是存放消息的队列。最简单的消息队列模型包括3个角色&#xff1a; 消息队列&#xff1a;存储和管理消息&#xff0c;也被称为消息代理&#xff08;Message Broker&#xff09;生产者&#xff1a;发送消息…...

android组件化

学习流程&#xff1a;1.开源最佳实践&#xff1a;Android平台页面路由框架ARouter-阿里云开发者社区 (aliyun.com)2.中文ARouter使用API&#xff1a;https://github.com/alibaba/ARouter/blob/master/README_CN.md3.看当前文档后面的代码4.这是通俗易懂的文章&#xff1a;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 个人能力&#xff1a;架构师的职责、技能和知识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.概述 在注解刚出现时&#xff0c;曾受到过好多程序员的鄙夷&#xff0c;觉得这就是多此一举的操作&#xff1b; 但随着时间的推移&#xff0c;越…...

webpack 的热更新是如何做到的?原理是什么?

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

嵌入式ARM设计编程(一) 简单数据搬移

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

【Selenium】十分钟手把手带你学会WebDriver API

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

3DMAX高级弯曲插件使用教程

3dMax高级弯曲插件是对3dmax原生“弯曲&#xff08;Bend&#xff09;”修改器的一个增强&#xff0c;给用户更多控制弯曲修改器的参数设置&#xff0c;它让用户输入宽度&#xff0c;插件脚本将移动中心以获得正确的宽度。 主要特性&#xff1a; - 使用智能捕捉捕捉到自定义网格…...

前端面试题之性能优化大杂烩

主要内容为下面几大类&#xff1a;移动端、图片、JavaScript、css、html、页面内容、服务器、cookie。 移动端性能优化&#xff1a; 保持单个文件小于25KB 移动网站页面要求下载资源&#xff0c;如果文件过大&#xff0c;会大大减慢页面加载速度。 打包内容为分段multipart文…...

SpringBoot+Vue实现养老智慧服务平台

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7/8.0 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;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 用户…...

智能三子棋(人机大战)—— 你会是最终赢家吗?万字讲解让你实现与自己对弈

魔王的介绍&#xff1a;&#x1f636;‍&#x1f32b;️一名双非本科大一小白。魔王的目标&#xff1a;&#x1f92f;努力赶上周围卷王的脚步。魔王的主页&#xff1a;&#x1f525;&#x1f525;&#x1f525;大魔王.&#x1f525;&#x1f525;&#x1f525; ❤️‍&#x1…...

【自制开发板】自制STM32F407开发板(含TFT 8080串口屏幕接口)

【2023 年 2 月 14 日】 许久没有更新&#xff0c;最近做了个小开发板玩了玩。更新一下吧&#xff0c;作为记录&#xff01;&#xff01; 主要是象试一下LVGL在STM32上的应用&#xff0c;所以开发板的大小都是基于屏幕大小来设计的。 分享出来&#xff0c;给大家一个板子结构…...

openvino yolov5/ssd 实时推流目标检测在html上显示

安装ffmepg并添加到环境变量中&#xff0c;流媒体使用m7s 运行效果 SSD&#xff1a;检测在10ms左右&#xff0c;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 也算是中低速&#xff08;有时也可以用作高速通信&#xff09;串行通信的范畴&#xff0c;但是一直还没真正实现过&#xff0c;所以此系列就 SPI的协议以及FPGA设计作几篇博客记录。欢迎订阅关注~ SPI 标准协议 x1模式…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

门静脉高压——表现

一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构&#xff1a;由肠系膜上静脉和脾静脉汇合构成&#xff0c;是肝脏血液供应的主要来源。淤血后果&#xff1a;门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血&#xff0c;引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...

【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析

1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器&#xff08;TI&#xff09;推出的一款 汽车级同步降压转换器&#xff08;DC-DC开关稳压器&#xff09;&#xff0c;属于高性能电源管理芯片。核心特性包括&#xff1a; 输入电压范围&#xff1a;2.95V–6V&#xff0c;输…...