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

[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]平衡二叉树——优化前后的两种方法

分析 根据平衡二叉树的定义&#xff0c;只需要满足&#xff1a;1、根节点两个子树的高度差不超过1&#xff1b;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 是一款专业的吉他、班卓琴和贝斯吉他降分器。在熟练的手中&#xff0c;它不仅可以让您创作&#xff0c;还可以编辑、聆听和录制&#xff0c;以及导入和导出乐谱。如果有人感兴趣的话&#xff0c;录音是在八个轨道上进行的&#xff0c;你可以为每个轨道单独…...

cocos tilemap的setTileGIDAt方法不实时更新

需要取消勾选 Enable Culling。同时代码添加&#xff1a;markForUpdateRenderData函数。 floor.setTileGIDAt(102427,newP.x,newP.y,0); //中心 floor.markForUpdateRenderData(); 具体问题参考官网说明&#xff1a; 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…...

铁合金电炉功率因数补偿装置设计

摘要 由于国内人民生活水平的提高&#xff0c;科技不断地进步&#xff0c;控制不断地完善&#xff0c;从而促使功率因数补偿装置在电力等系统领域占据主导权&#xff0c;也使得功率因数补偿控制系统被广泛应用。在铁合金电炉系统设计领域中&#xff0c;功率因数补偿控制成为目前…...

表格识别软件:科技革新引领行业先锋,颠覆性发展前景广阔

表格识别软件的兴起背景可以追溯到数字化和自动化处理的需求不断增加的时期。传统上&#xff0c;手动处理纸质表格是一项费时费力的工作&#xff0c;容易出现错误&#xff0c;效率低下。因此&#xff0c;开发出能够自动识别和提取表格数据的软件工具变得非常重要。 随着计算机…...

【Redis】高并发分布式结构服务器

文章目录 服务端高并发分布式结构名词基本概念评价指标1.单机架构缺点 2.应用数据分离架构应用服务集群架构读写分离/主从分离架构引入缓存-冷热分离架构分库分表&#xff08;垂直分库&#xff09;业务拆分⸺微服务 总结 服务端高并发分布式结构 名词基本概念 应⽤&#xff0…...

微信小程序拍照页面自定义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

一、微网系统运行优化模型 微电网优化模型介绍&#xff1a; 微电网多目标优化调度模型简介_IT猿手的博客-CSDN博客 二、进化场优化算法EFO 进化场优化算法&#xff08;Evolutionary Field Optimization&#xff0c;EFO&#xff09;由Baris Baykant Alagoz等人于2022年提出&…...

推荐算法面试

当然可以&#xff0c;请看下面的解释和回答&#xff1a; 一面&#xff08;7.5&#xff09; 问题&#xff1a;推荐的岗位和其他算法岗&#xff08;CV&#xff0c;NLP&#xff09;有啥区别&#xff1f; 解释&#xff1a; 面试官可能想了解你对不同算法岗位的理解&#xff0c;包…...

长图切图怎么切

用PS的切片工具 切片工具——基于参考线的切片——ctrl&#xff0b;shift&#xff0b;s 过长的图片怎么切 ctrl&#xff0b;alt&#xff0b;i 查看图片的长宽看图片的长宽来切成两个板块&#xff08;尽量中间切成两半&#xff09;用选区工具选中下半部分的区域——在选完时不…...

动手学深度学习 - 学习环境配置

学习环境配置 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 参考&#xff1a; https://www.jb51.n…...

洛谷 B2004 对齐输出 C++代码

目录 推荐专栏 题目描述 AC Code 切记 推荐专栏 http://t.csdnimg.cn/Z1tCAhttp://t.csdnimg.cn/Z1tCA 题目描述 题目网址&#xff1a;对齐输出 - 洛谷 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&#xff0c;惊呼已经不认识seccomp了&#xff0c;在被一道盲打题折磨了一整天之后&#xff0c;实在是不想面向题目高强度学习了。…...

Linux指令【上】

目录 目录结构 ls cd stat touch mkdir whoami 查看当前帐号是谁 who 查看当前有哪些人在使用 pwd 当前的工作目录 目录结构 目录结构就是一颗多叉树的样子 路径 我们从 / 目录开始&#xff0c;定位一个叶子文件的…...

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

人们发现&#xff0c;一种新的网络攻击活动正在使用 MSIX&#xff08;一种 Windows 应用程序打包格式&#xff09;来感染 Windows PC&#xff0c;并通过将隐秘的恶意软件加载程序放入受害者的 PC 中来逃避检测。 Elastic Security Labs 的研究人员发现&#xff0c;开发人员通常…...

干货!数字IC后端入门学习笔记

很多同学想要了解IC后端&#xff0c;今天大家分享了数字IC后端的学习入门笔记&#xff0c;供大家学习参考。 很多人对于后端设计的概念比较模糊&#xff0c;需要做什么也都不甚清楚。 有的同学认为就是跑跑 flow、掌握各类工具。 事实上&#xff0c;后端设计的工作远不止于此。…...

力扣:144. 二叉树的前序遍历(Python3)

题目&#xff1a; 给你二叉树的根节点 root &#xff0c;返回它节点值的 前序 遍历。 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 示例&#xff1a; 示例 1&#xff1a; 输…...

【数据挖掘 | 数据预处理】缺失值处理 重复值处理 文本处理 确定不来看看?

&#x1f935;‍♂️ 个人主页: AI_magician &#x1f4e1;主页地址&#xff1a; 作者简介&#xff1a;CSDN内容合伙人&#xff0c;全栈领域优质创作者。 &#x1f468;‍&#x1f4bb;景愿&#xff1a;旨在于能和更多的热爱计算机的伙伴一起成长&#xff01;&#xff01;&…...

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

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

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...