[java/力扣110]平衡二叉树——优化前后的两种方法

分析
根据平衡二叉树的定义,只需要满足:1、根节点两个子树的高度差不超过1;2、左右子树都为平衡二叉树
代码
public class BalancedBinaryTree {public class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val = val;}}public boolean isBalanced(TreeNode root) {if(root == null){return true;}//判断左子树是否为平衡二叉树int leftH = getHeight(root.left);//判断右子树是否为平衡二叉树int rightH = getHeight(root.right);//当满足三个条件时返回turereturn Math.abs(leftH-rightH)<2&&isBalanced(root.left)&&isBalanced(root.right);}//获取树的高度public int getHeight(TreeNode root){if(root == null){return 0;}//获取左子树高度int leftH = getHeight(root.left);//获取右子树高度int rightH = getHeight(root.right);//返回左右子树的最大值+1(加上根节点高度),即为树的高度return ((leftH > rightH) ? (leftH+1):(rightH+1));}
}
进行优化
但是这样的做法,每对一个结点进行平衡判定就要求一次 以该结点为根节点的树的高度。时间复杂度太大
所以我们在求高度的时候就进行判定是否平衡。

在求高度的时候就进行平衡判定,如果其中一颗子树不平衡,就直接返回-1(因为高度是不能为-1的),子树为空则返回0。
如下图所示。对于3为根节点的二叉树,左树返回1,右树返回0;然后对于9为根节点的二叉树,左子树返回2,右子树返回0;对于以3为根节点的二叉树,左子树返回-1(说明左子树不平衡),右子树返回-1(说明右子树不平衡),所以以3为根节点的二叉树返回-1.
同时要注意:存在一个根节点,其左子树不平衡返回-1,右子树为空返回0,但此时左右子树高度差的绝对值还是1.所以我们要对此做出限制
优化后的代码
public class Test3 {public class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val = val;}}public boolean isBalanced(TreeNode root) {return getHeight(root) >= 0;}//获取树的高度public int getHeight(TreeNode root){if(root == null){return 0;}//获取左子树高度int leftH = getHeight(root.left);//获取右子树高度int rightH = getHeight(root.right);/*如果一个节点左树不平衡(返回-1),右树为空(返回0)。它不是个平衡二叉树,但是它满足左右子树高度差为1* 所以这里限制左右子树高度都大于0*/if (leftH >= 0 && rightH >= 0 &&Math.abs(leftH - rightH)<=1){return Math.max(leftH,rightH)+1;}else {return -1;}/*为什么不能在第一个不平衡的二叉树出现时就结束?* 因为你是判断高度的方法,不是判断平衡的方法。* false应该在另一个方法中被返回*/}
}
相关文章:
[java/力扣110]平衡二叉树——优化前后的两种方法
分析 根据平衡二叉树的定义,只需要满足:1、根节点两个子树的高度差不超过1;2、左右子树都为平衡二叉树 代码 public class BalancedBinaryTree {public class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int va…...
吉他、班卓琴和贝斯吉他降分器:Arobas Music Guitar 8.1.1
Arobas Music Guitar 是一款专业的吉他、班卓琴和贝斯吉他降分器。在熟练的手中,它不仅可以让您创作,还可以编辑、聆听和录制,以及导入和导出乐谱。如果有人感兴趣的话,录音是在八个轨道上进行的,你可以为每个轨道单独…...
cocos tilemap的setTileGIDAt方法不实时更新
需要取消勾选 Enable Culling。同时代码添加:markForUpdateRenderData函数。 floor.setTileGIDAt(102427,newP.x,newP.y,0); //中心 floor.markForUpdateRenderData(); 具体问题参考官网说明: Cocos Creator 3.2 手册 - 项目设置...
机器学习---使用 TensorFlow 构建神经网络模型预测波士顿房价和鸢尾花数据集分类
1. 预测波士顿房价 1.1 导包 from __future__ import absolute_import from __future__ import division from __future__ import print_functionimport itertoolsimport pandas as pd import tensorflow as tftf.logging.set_verbosity(tf.logging.INFO) 最后一行设置了Ten…...
铁合金电炉功率因数补偿装置设计
摘要 由于国内人民生活水平的提高,科技不断地进步,控制不断地完善,从而促使功率因数补偿装置在电力等系统领域占据主导权,也使得功率因数补偿控制系统被广泛应用。在铁合金电炉系统设计领域中,功率因数补偿控制成为目前…...
表格识别软件:科技革新引领行业先锋,颠覆性发展前景广阔
表格识别软件的兴起背景可以追溯到数字化和自动化处理的需求不断增加的时期。传统上,手动处理纸质表格是一项费时费力的工作,容易出现错误,效率低下。因此,开发出能够自动识别和提取表格数据的软件工具变得非常重要。 随着计算机…...
【Redis】高并发分布式结构服务器
文章目录 服务端高并发分布式结构名词基本概念评价指标1.单机架构缺点 2.应用数据分离架构应用服务集群架构读写分离/主从分离架构引入缓存-冷热分离架构分库分表(垂直分库)业务拆分⸺微服务 总结 服务端高并发分布式结构 名词基本概念 应⽤࿰…...
微信小程序拍照页面自定义demo
api文档 <template><div><imagemode"widthFix"style"width: 100%; height: 300px":src"imageSrc"v-if"imageSrc"></image><camerav-else:device-position"devicePosition":flash"flash&qu…...
单目标应用:进化场优化算法(Evolutionary Field Optimization,EFO)求解微电网优化MATLAB
一、微网系统运行优化模型 微电网优化模型介绍: 微电网多目标优化调度模型简介_IT猿手的博客-CSDN博客 二、进化场优化算法EFO 进化场优化算法(Evolutionary Field Optimization,EFO)由Baris Baykant Alagoz等人于2022年提出&…...
推荐算法面试
当然可以,请看下面的解释和回答: 一面(7.5) 问题:推荐的岗位和其他算法岗(CV,NLP)有啥区别? 解释: 面试官可能想了解你对不同算法岗位的理解,包…...
长图切图怎么切
用PS的切片工具 切片工具——基于参考线的切片——ctrl+shift+s 过长的图片怎么切 ctrl+alt+i 查看图片的长宽看图片的长宽来切成两个板块(尽量中间切成两半)用选区工具选中下半部分的区域——在选完时不…...
动手学深度学习 - 学习环境配置
学习环境配置 1、安装 Miniconda1.1 下载 miniconda31.2 环境变量配置1.3 安装成功测试1.4 配置文件1.5 使用conda创建、使用、删除环境1.6 conda 常用命令 2、使用 miniconda 安装 d2l2.1 下载 d2l 安装包2.2 安装 d2l 1、安装 Miniconda 参考: https://www.jb51.n…...
洛谷 B2004 对齐输出 C++代码
目录 推荐专栏 题目描述 AC Code 切记 推荐专栏 http://t.csdnimg.cn/Z1tCAhttp://t.csdnimg.cn/Z1tCA 题目描述 题目网址:对齐输出 - 洛谷 AC Code #include<bits/stdc.h> using namespace std; typedef long long ll; int main() { int a,b,c;cin&g…...
seccomp学习 (1)
文章目录 0x01. seccomp规则添加原理A. 默认规则B. 自定义规则 0x02. seccomp沙箱“指令”格式实例Task 01Task 02 0x03. 总结 今天打了ACTF-2023,惊呼已经不认识seccomp了,在被一道盲打题折磨了一整天之后,实在是不想面向题目高强度学习了。…...
Linux指令【上】
目录 目录结构 ls cd stat touch mkdir whoami 查看当前帐号是谁 who 查看当前有哪些人在使用 pwd 当前的工作目录 目录结构 目录结构就是一颗多叉树的样子 路径 我们从 / 目录开始,定位一个叶子文件的…...
RK3568-clock
pll锁相环 总线 gating rk3568.dtsi pmucru: clock-controller@fdd00000 {compatible = "rockchip,rk3568-pmucru";reg = <0x0 0xfdd00000 0x0 0x1000>;rockchip,grf = <&grf>;rockchip,pmugrf = <&pmugrf>;#clock-cells = <1>;#re…...
新恶意软件使用 MSIX 软件包来感染 Windows
人们发现,一种新的网络攻击活动正在使用 MSIX(一种 Windows 应用程序打包格式)来感染 Windows PC,并通过将隐秘的恶意软件加载程序放入受害者的 PC 中来逃避检测。 Elastic Security Labs 的研究人员发现,开发人员通常…...
干货!数字IC后端入门学习笔记
很多同学想要了解IC后端,今天大家分享了数字IC后端的学习入门笔记,供大家学习参考。 很多人对于后端设计的概念比较模糊,需要做什么也都不甚清楚。 有的同学认为就是跑跑 flow、掌握各类工具。 事实上,后端设计的工作远不止于此。…...
力扣:144. 二叉树的前序遍历(Python3)
题目: 给你二叉树的根节点 root ,返回它节点值的 前序 遍历。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 示例: 示例 1: 输…...
【数据挖掘 | 数据预处理】缺失值处理 重复值处理 文本处理 确定不来看看?
🤵♂️ 个人主页: AI_magician 📡主页地址: 作者简介:CSDN内容合伙人,全栈领域优质创作者。 👨💻景愿:旨在于能和更多的热爱计算机的伙伴一起成长!!&…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
