[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内容合伙人,全栈领域优质创作者。 👨💻景愿:旨在于能和更多的热爱计算机的伙伴一起成长!!&…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
鱼香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…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...
DAY 26 函数专题1
函数定义与参数知识点回顾:1. 函数的定义2. 变量作用域:局部变量和全局变量3. 函数的参数类型:位置参数、默认参数、不定参数4. 传递参数的手段:关键词参数5 题目1:计算圆的面积 任务: 编写一…...
用递归算法解锁「子集」问题 —— LeetCode 78题解析
文章目录 一、题目介绍二、递归思路详解:从决策树开始理解三、解法一:二叉决策树 DFS四、解法二:组合式回溯写法(推荐)五、解法对比 递归算法是编程中一种非常强大且常见的思想,它能够优雅地解决很多复杂的…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...
