当前位置: 首页 > 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模式…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

DAY 47

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

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

[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模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

深度学习水论文:mamba+图像增强

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

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...