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

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...