[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内容合伙人,全栈领域优质创作者。 👨💻景愿:旨在于能和更多的热爱计算机的伙伴一起成长!!&…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
