平衡二叉树的判定

news/2024/5/5 15:43:51/文章来源:https://blog.csdn.net/qx020814/article/details/127313612

修仙公元2022年,一男子试图突破二叉树大关,遇一问题:

给定一个二叉树的根节点,请判断是否为平衡二叉树(左右节点的高度绝对子小于等于1)。

该男子使用层序遍历大法,信誓旦旦的前往考核地点。

结果可想而自:

啊——咚——啃——!!

以失败告终。。。。

最终求助于深山老者,得一秘籍:

 老者问题:何为平衡二叉树?

男子答曰:其左右节点高度相减,绝对值小于等于1着为平衡二叉树、

老者再问:何为二叉树高度?

男子复答曰:一节点左右节点皆为null,高度则为1,再往上一层则+1、

 老者抚理胡须曰:很好!我这里有一本平衡二叉树秘籍,我与你有缘,赠送与你,望发扬光大!

老者说完,化作一缕青烟消失在时空当中————

———————————————————————————————————————————


坑爹书籍之一,就一张纸。。。。。。

 不过聪明的男子看出了其中的奥秘!

首先确定递归的参数:传入节点

确定返回值:每层的高度,int

递归条件:不为空时。

还有一些细节:

这里我们将返回值为-1定为此二叉树不为平衡二叉树。

 public boolean isBalanced(TreeNode root) {return dfs(root)==-1?false:true;}int dfs(TreeNode root){if(root==null){return 0;}int l=dfs(root.left);if(l==-1){return -1;}int r=dfs(root.right);if(r==-1){return -1;}return Math.abs(l-r)>1?-1:1+Math.max(l,r);}

 当左右节点任何一个节点返回-1时,就说明下面已经不满足平衡二叉树的定义了,就可以继续返回-1了。

第二点:下一层的高度是等于本层左右节点最大值+1.这里大家画一个二叉树,从下往上画一遍就懂了。

男子一脸骄傲的样子,兴冲冲跑去测试,过了!

结果门后还有门,无穷无尽,男子当场暴毙!卒!

                                                                                                                                结章——

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_23441.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

开源人脸识别系统compareface介绍

Exadel CompreFace是一种免费的open-source人脸识别服务,无需事先具备机器学习技能,即可轻松集成到任何系统中。CompreFace为人脸识别、人脸验证、人脸检测、里程碑检测、年龄和性别识别提供了REST API,并且易于与docker一起部署。 https://…

基于SSM的教师管理系统

项目技术栈 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:采用HTML和Vue相结合开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目&…

【车道线检测】FOLOLane解读

文章目录一、概览二、具体阐述1. Introduction2. 模型head介绍(1) Key points estimation--网络第一个head(2) Local geometry construction--网络第二个head3. Network architecture4. Decoder for global geometry(1) Greedy decoder(精度高,但是效率低…

事务到底是隔离还是不隔离?

1. 引例 之前我们探讨过可重复读隔离级别下,事务T启动的时候会创建一个视图read-view。在事务T执行期间,即使有其他事务修改了数据,事务T看到的也是跟启动时一样的。 但是上次讲到行锁的时候,当事务T要更新当前行的时候&#xf…

Spring-Framework-ioc-4

1前言 2基本原理 3IOC容器 4Bean 5依赖 5.1依赖注入 5.2自动装配 自动装配,是一种自动化地进行依赖注入的机制,IOC容器使用此机制实现bean之间依赖关系的自动绑定,该机制具有如下的优点: 不需要显式地指定依赖的属性域、构…

基于STC89C52单片机的蔬菜大棚实时温度测量控制系统

目录 摘要 …………………………………………………………………………………I ABSTRACT II 第一章 设计任务及方案分析 1 1.1 设计任务及要求 1 1.2 设计总体方案及方案论证 1 1.3 温度测量的方案与分析 1 1.31芯片选择 1 1.32实现方法简介 2 1.33 方案设计 2 第二章 芯片简介…

Java基础(二):集合、IO流(Zip压缩输入/输出流等)、File文件类、反射、枚举

Java基础(一):编译和解释、数据类型、变量作用域、String常用方法、数组、面向对象、异常 Java基础(二):集合、IO流(Zip压缩输入/输出流等)、File文件类、反射、枚举 Java异常、继承结构、处理异常、自定义异常、SpringBoot中全…

数据库学习记录2

数据库学习记录1介绍了DDL (Data Definition Language) 数据定义语言。 在数据库学习记录2中,我们介绍常见的数据类型; 主要分为三类:数值类型、字符串类型、日期时间类型。 数值类型 类型大小有符号范围无符号范围描述TINYINT1byte(-128&…

生成模型笔记(七):自回归模型

有鸟止南方之阜,三年不翅,不飞不鸣,嘿然无声,此为何名? 第七部分 深度自回归模型(Deep Autoregressive Model, DARM) 参考内容 https://jmtomczak.github.io/blog/2/2_ARM.html A…

第二十三:Fiddler抓包教程(23)-Fiddler如何优雅地在正式和测试环境之间来回切换-上篇

一.简介 1.在开发或者测试的过程中,由于项目环境比较多,往往需要来来回回地反复切换,那么如何优雅地切换呢? 二.实际工作场景 1.问题场景 1.1.已发布线上APP出现接口错误,如何测试线上APP访问本地请求?…

QFramework v1.0 使用指南 介绍篇:01. 简介

01. 简介 大家好,我是 QFramework 的作者 凉鞋,QFramework 从第一次代码提交到现在快 7 年了(2015 年 12 月 ~ 2022 年 10 月)了,而经过了 7 年时间的打磨,我们终于迎来了 v1.0 版本。 此教程&#xff0c…

Macos/linux g++ 安装OpenCV环境

本文前半部分主要翻译官方文档的东西 https://docs.opencv.org/4.x/d0/db2/tutorial_macos_install.html 依赖: CMake 3.9 or higher Git Python 2.7 or later and Numpy 1.5 or later大家都是程序员自己安装一下吧 在 relese 这里下载一下源代码: htt…

第三章:为组件库添加规范【前端工程化入门-----从零实现一个react+ts+vite+tailwindcss组件库】

第三章:为组件库添加规范 本章我们会用 eslint、prettier以及Husky 为组件库添加规范; 前置知识: eslint、prettier和husky各有什么作用? eslint是代码检查工具,你可以配置eslint,然后通过lint命令检测…

打游戏哪款蓝牙耳机好?四款适合打游戏的蓝牙耳机推荐

现在年轻人最离不开的就是手游,蓝牙耳机可谓是手机游戏的最佳搭档,一副好的蓝牙耳机可以为游戏带来很完美的助力,延迟低的蓝牙耳机可以实现更好的游戏体验感,那么接下来推荐四款适合打游戏的蓝牙耳机。 1、南卡小音舱蓝牙耳机 佩…

2022年全国大学生数学建模美赛E题NPP数据获取

今年的数学建模美赛终于开始了!令我感到欣喜的是,今年E题竟然和地理遥感专业息息相关。E题是分析生态环境方面的!因此,有很多小伙伴来询问咨询如何解决这道题目。有些小伙伴,还咨询如何使用CASA软件来计算NPP数据&…

Flink SQL使用Catalog消费Kafka时,多个Source读取同一主题解决方案

一、Catalog定义 Catalog 提供了元数据信息,例如数据库、表、分区、视图以及数据库或其他外部系统中存储的函数和信息。数据处理最关键的方面之一是管理元数据。 元数据可以是临时的,例如临时表、或者通过 TableEnvironment 注册的 UDF。 元数据也可以是…

apollo在虚拟机下部署遇到的坑

目录问题描述解决方法编译问题总结问题描述 ​   其实在虚拟机下部署apollo网上是有线程教程的。可以参考在虚拟机上安装运行百度Apollo 6.0,Apollo 6.0 安装完全指南。我依靠这两个指南准备部署的是apollo 7.0,事实证明虽然版本不同,但部…

1、6边距复合属性

提示:文章写完后,padding可以有到四个值。 1、语法: div{ padding:“50px”; padding:“5px 10px”; padding:“5px 10px 20px”; padding:“5…

flex竖排列元素排列方向

flex竖排列元素排列方向一、flex-direction: (元素排列方向) ※ flex-direction:row (横向从左到右排列==左对齐)※ flex-direction:row-reverse (与row 相反)※ flex-direction:column (从上往下排列==顶对齐)※ flex-direction:column-reverse (与column 相反) 二…

基于导频的信道估计实现

目录 零、前言 一、为什么要信道估计 二、导频的概念 (1)为什么要有导频 (2)导频在信道估计中作用 (3)关于导频序列的补充 三、最小二乘法估计 (1)LS信道估计算法分析 &…