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

LeetCode-110. 平衡二叉树

目录

    • 题目分析
    • 递归法
    • 题外话

题目来源
110. 平衡二叉树

题目分析

平很二叉树:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
二叉树节点的深度和二叉树节点的高度
在这里插入图片描述

递归法

递归三步曲

  • 1.明确递归函数的参数和返回值

参数:当前传入节点。
返回值:以当前传入节点为根节点的树的高度。
那么如何标记左右子树是否差值大于1呢?
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了,还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了,可以返回-1 来标记已经不符合平衡树的规则了。
代码如下:

int getHeight(TreeNode root)
  • 2.明确终止条件

递归的过程中依然是遇到空节点了为终止,返回0,表示当前节点为根节点的树高度为0
代码如下:

        if(root == null){return 0;}
  • 3.明确单层递归的逻辑

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢?当然是其左子树高度和其右子树高度的差值。
分别求出其左右子树的高度,然后如果差值小于等于1,则返回当前二叉树的高度,否则返回-1,表示已经不是二叉平衡树了。
代码如下:

        int leftHeight = getHeight(root.left);   //左if(leftHeight == -1){return -1;}int rightHeight = getHeight(root.right);   //右if(leftHeight == -1){return -1;}int result;if(Math.abs(leftHeight-rightHeight)>1){        //中return -1;}else{result = Math.max(leftHeight,rightHeight)+1;}return result;

整体递归代码如下:

class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}public static int getHeight(TreeNode root){if(root == null){return 0;}int leftHeight = getHeight(root.left);   //左if(leftHeight == -1){return -1;}int rightHeight = getHeight(root.right);   //右if(rightHeight == -1){return -1;}int result;if(Math.abs(leftHeight-rightHeight)>1){        //中return -1;}else{result = Math.max(leftHeight,rightHeight)+1;}return result;}
}

在这里插入图片描述

题外话

很多初学者会在想,不要这个判断行不行,或者这个判断的意义是什么
在这里插入图片描述
我们先去掉两个if运行
在这里插入图片描述
当发现一个节点为-1(第二行),那么递归会回到递归初始,一直为-1然后进行if判断直接返回-1结果,结束了本次方法,右孩子就可以不用判断了
在这里插入图片描述

相关文章:

LeetCode-110. 平衡二叉树

目录题目分析递归法题外话题目来源 110. 平衡二叉树 题目分析 平很二叉树:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 二叉树节点的深度和二叉树节点的高度 递归法 递归三步曲 1.明确递归函数的参数和返回值 参数:当前传入节点。 返回值…...

Python蓝桥杯训练:基本数据结构 [链表]

Python蓝桥杯训练:基本数据结构 [链表] 文章目录Python蓝桥杯训练:基本数据结构 [链表]一、链表理论基础知识二、有关链表的一些常见操作三、力扣上面一些有关链表的题目练习1、[移除链表元素](https://leetcode.cn/problems/remove-linked-list-element…...

华为OD机试 - 找字符(Python)| 真题+思路+代码

找字符 题目 给定两个字符串, 从字符串2中找出字符串1中的所有字符, 去重并按照 ASCII 码值从小到大排列。 输入 字符范围满足 ASCII 编码要求, 输入字符串1长度不超过1024, 字符串2长度不超过100。 输出描述 按照 ASCII 由小到大排序 示例一 输入 bach bbaaccddf…...

使用继承与派生的6大要点

概述 面向对象编程技术非常看重软件的可重用性,在C中,可重用性是通过继承机制来实现的。继承机制允许程序员在保持原有类的数据和功能的基础上进行扩展,增加新的数据和功能,从而构成一个新的类,也称为派生类。原有类&a…...

加一-力扣66-java高效方案

一、题目描述给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外,这个整数不会以零开头。示例 1:输入:di…...

记一次 .NET 某游戏网站 CPU爆高分析

一:背景 1. 讲故事 这段时间经常有朋友微信上问我这个真实案例分析连载怎么不往下续了,关注我的朋友应该知道,我近二个月在研究 SQLSERVER,也写了十多篇文章,为什么要研究这东西呢? 是因为在 dump 中发现…...

集群使用——资源管理和租户创建

概述 OceanBase 数据库是多租户的分布式数据库,租户使用的资源建立在资源池上。资源池包含了资源单元,而资源单元则规定了具体资源的量化(如 CPU、Memory、Disk_Size 和 IOPS 等)。 创建租户前,必须规定租户使用的资源…...

谷歌浏览器登录失败,提示【无法同步到“...@gmail.com”】

首先安装Chrome同步助手(Chrome-Sync-Helper,看了很多博客,谷歌浏览器同步问题好像都要用这个),改成.rar,解压,文件夹_metadata重命名为metadata,然后添加到谷歌浏览器的扩展程序中。…...

75 111111

选择题(共75题,合计75.0分) 1. 选项ABCD中显示了所创造的商业价值以及在产品中实施各种功能需要进行的开发工作。团队应优先实施哪项功能? The business value created and the development effort needed to implement the various features in the product are sh…...

分销系统逻辑

相关概念 主营商户: 提供分销商品和佣金的商户分销商: 拥有自己的销售渠道,能够帮助推动产品销售的个人或商户消费者: 购买分销商品的人。佣金: 主营商户返还给经销商的比例抽成 分销功能设计 (1)分销商准入规则设计 无规则: 没有分销商的准入门槛限制&#xf…...

MySQL视图特性

文章目录MySQL视图特性基本使用准备测试表创建视图修改视图影响基表修改基表影响视图删除视图视图规则和限制MySQL视图特性 视图的概念 视图是一个虚拟表,其内容由查询定义,同真实的表一样,视图包含一系列带有名称的列和行数据。视图中的数据…...

RabbitMQ详解(二):Docker安装RabbitMQ

在Docker上安装部署RabbitMQ方便快捷,不需要额外安装Erlang环境,所以写该篇文章先来介绍如何在Docker上部署RabbitMQ。 一、安装并运行 (1)、在docker hub 中查找rabbitmq镜像 docker search rabbitmq:3.9.12-management带有“mangement”的版本&…...

如何使用代码注释:关于JavaScript与TypeScript 注释和文档的自动生成

如何使用代码注释:关于JavaScript与TypeScript 注释和文档的自动生成jcLee95:https://blog.csdn.net/qq_28550263?spm1001.2101.3001.5343 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/detail…...

Echarts 设置面积区域图(areaStyle核心)

第011个点击查看专栏目录Echarts折线区域面积图的视觉效果更加饱满丰富,在系列不多的场景下尤其适用。区域面积图将折线到坐标轴的空间设置背景色,用区域面积表达数据。通过 areaStyle 设置折线图的填充区域样式,将其设为为 {} 表示使用默认…...

pandas——字符串处理【建议收藏】

pandas——字符串处理 作者:AOAIYI 创作不易,如果觉得文章不错或能帮助到你学习,记得点赞收藏评论一下哦 文章目录pandas——字符串处理一、实验目的二、实验原理三、实验环境四、实验内容五、实验步骤1.cat() 拼接字符串2.split()切片字符串…...

反射,枚举,lambda表达式

目录 1、反射 1.1 基本概念 1.2 反射相关的类 1.3 创建 Class 对象 1.4 反射的使用 1.4.1 通过反射创建对象: 1.4.2 获取私有的构造方法 1.4.3 获取私有的成员变量 1.4.4 获取私有的方法 1.5 总结 2、枚举 2.1 认识枚举 2.2 使用枚举 2.3 枚举与反射…...

.Net Core对于RabbitMQ封装分布式事件总线

首先我们需要了解到分布式事件总线是什么; 分布式事件总线是一种在分布式系统中提供事件通知、订阅和发布机制的技术。它允许多个组件或微服务之间的协作和通信,而无需直接耦合或了解彼此的实现细节。通过事件总线,组件或微服务可以通过发布…...

GPIO功能描述

GPIO 文章目录 GPIO1. 功能描述1.1 OSCI/OSCO 引脚1.3 HSEIN/HSEOUT引脚1.2 Bit-Band1.4 VRTCAFx引脚1.5 EWKUPx引脚1.6 QSPI0 引脚1.7 LVDIN引脚1.8 SARADC引脚1.9 ADCIN引脚2. 测试项描述2.1 PAD Location2.2 LBOR和BOR复位2.3 驱动能力2.4 模拟态\高阻态2.5 SWD\JTAG2.6 输出…...

指派问题与匈牙利法讲解

指派问题概述:实际中,会遇到这样的问题,有n项不同的任务,需要n个人分别完成其中的1项,每个人完成任务的时间不一样。于是就有一个问题,如何分配任务使得花费时间最少。通俗来讲,就是n*n矩阵中&a…...

day5——冒泡排序,选择排序和插入排序的学习

选择排序冒泡排序插入排序 选择排序 选择排序的基本思路就是: 首先假定第一个的下表为所有元素中最小的一个, 然后用后面的每一个元素跟这个元素进行比较, 如果后面的元素比这个元素更小一点, 那么就将找到的最小的元素的下标和…...

Windows 数据类型 (Windows Data Types)

参考:https://learn.microsoft.com/en-us/windows/win32/winprog/windows-data-types 要求 要求值最低受支持的客户端Windows XP [仅限桌面应用]最低受支持的服务器Windows Server 2003 [仅限桌面应用]HeaderBaseTsd.h;WinDef.h;WinNT.hAPIENTRY 系统函数的调用约…...

九龙证券|本周5只新股申购,特斯拉、蔚来、理想的供应商来A股了!

据现在组织,2月13日到17日共有5只新股申购,其间上证主板2只,深证主板1只,北交所2只。 2月14日发动打新的深证主板新股多利科技成立于2010年,是一家专心于轿车冲压零部件及相关模具的开发、出产与出售的企业。从2020年…...

设计模式(持续更新)

本文主要是记录java的设计模式在实际工作中的应用案例,或者是对设计模式的个人理解及备忘 一、单例模式Singleton 工作场景(静态类): 在外部系统对接中,需要调用外部系统A的接口,但是接口是有身份校验的…...

Prometheus 告警规则

Prometheus 告警规则 Prometheus官方内置的第三方报警通知包括:邮件、 即时通讯软件(如Slack、Hipchat)、移动应用消息推送(如Pushover)和自动化运维工具(例如:Pagerduty、Opsgenie、Victorops) Promethe…...

mulesoft MCIA 破釜沉舟备考 2023.02.13.02

mulesoft MCIA 破釜沉舟备考 2023.02.13.03 1. According to MuleSoft, which deployment charcateristic applies to a microservices application architecture?2. A mule application designed to fulfil two requirements3. A mule application must periodically process…...

获取DLL运行时路径的方法

之前项目中发现的问题,记录下解决方案1. 问题背景OVVRNTool项目中,底层图像基本操作功能由DLL库函数提供,上层基于DLL封装了两个应用CMD和GUI,然后通过Qt打包分发;发布是直接采用绿色免安装的方式打包,具体…...

“华为杯”研究生数学建模竞赛2006年-【华为杯】D题:学生面试中教师安排的优化与算法(附获奖论文)

赛题描述 高校自主招生是高考改革中的一项新生事物,现在仍处于探索阶段。某高校拟在全面衡量考生的高中学习成绩及综合表现后再采用专家面试的方式决定录取与否。该校在今年自主招生中,经过初选合格进入面试的考生有N人,拟聘请老师M人。每位学生要分别接受4位老师(简称该学…...

【JavaScript】复习 【对象参数】【函数参数】

js不会检查任何参数类型,任何参数都可以作为参数传递 1、对象参数 改变量随便改,改对象要看这个对象是不是有多个变量同时指向这个对象 const 用来定义常量,只能赋值一次。 变量------->对象------->属性 被const修饰的对象 …...

如何批量提取文件名到excel表格?

批量提取文件名到excel表格?关于这个问题相信很多人都遇到过,大多数人在第一次碰到的时候都不知道如何下手,大家都会立即在百度里面搜索相关方法教程,小编也试着搜索了一下,发现找到的很多方法都大同小异,需…...

CUDA线程层次一文搞懂|参加CUDA线上训练营

设备术语 Host:CPU 和 内存 (host memory)Device:GPU 和显存 (device memory) CUDA 线程层次 CUDA 线程层次分为: Thread 所有线程执行相同的核函数并行执行 Thread Block 执行在一个 Streaming Multiprocessor (SM&#xff09…...

.net 大型网站开发/广州公关公司

机器学习(四)变量选择技术----------岭回归,Lasso 我们回顾一下之前线性回归模型里面的一元线性回归模型和多元线性回归模型,里面在谈论如何找到最佳系数时,使用的是最小二乘法,在这里我们先把多元线性回归的最小二乘解简化表达一…...

目前最流行网站开发软件/百度一下百度网页官

反集的反集不是朋友。。。要是把他们合并便多了 //并查集反集的思想 #include<cstdio> #include<iostream> using namespace std; int n,m; int flag; int flag1[9999]; int f[2500]; int find(int x) {if(f[x]!x) f[x]find(f[x]); return f[x];}//找祖先路径压…...

北京著名网站建设公司/个人网页设计作品欣赏

感谢分享 http://blog.csdn.net/uikoo9/article/details/43451377 内容简介 介绍目前前端人员开发app的几种方法&#xff0c;具体介绍hbuilder开发app&#xff0c;一扇赞新的大门~ 无所不能的js 最开始js仅仅局限于网页上一些效果&#xff0c;操作网页内容等&#xff0c; 但是…...

网站模板站的模板展示怎么做的/网站优化与seo

方法一&#xff1a;伪列布局法(利用背景图)所谓伪列布局法&#xff0c;就是设计一个背景图像&#xff0c;利用背景图像来模拟栏目的背景。如&#xff0c;使用Photoshop设计一个长方形的背景图&#xff0c;长度与页面宽度保持一致&#xff0c;高度任意。代码中要用到的背景图&am…...

软件园二期做网站的公司/外贸seo优化公司

oracle 中的常量和变量:变量&#xff1a;通过变量&#xff0c;可以把需要的参数传递进来&#xff0c;经过处理后还可以把值传出去&#xff0c;最终返回给用户。常量&#xff1a;常量是代码中固化的信息&#xff0c;常量的值从定义开始就是固定的。常量主要用于为程序提供固定和…...

一个网站seo做哪些工作内容/网站整站优化

1 引言 linux中进行C/C开发&#xff0c;一般都是先用编辑器写好代码&#xff0c;然后使用gcc工具来编译程序。 文件数量不多的工程&#xff0c;可以直接敲gcc命令进行编译。对于文件较多的工程&#xff0c;就要使用Makefile来管理代码的编译了。 而手动编写Makefile其实也是…...