当前位置: 首页 > 编程日记 > 正文

python实现平衡二叉树_LeetCode 110. 平衡二叉树 | Python

# 110. 平衡二叉树

---

题目来源:力扣(LeetCode)[https://leetcode-cn.com/problems/balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree)

## 题目

---

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

**示例 1:**

```bash

给定二叉树 [3,9,20,null,null,15,7]

3

/ \

9  20

/  \

15   7

返回 true 。

```

**示例 2:**

```bash

给定二叉树 [1,2,2,3,3,null,null,4,4]

1

/ \

2   2

/ \

3   3

/ \

4   4

返回 false 。

```

## 解题思路

---

### 思路:递归(自顶向下,自底向上)

审题,题目要求给定的二叉树是否是高度平衡二叉树。关于高度平衡二叉树,题目给的定义是:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

也就是说,只有所有子树都是平衡二叉树的条件下,整个二叉树才是平衡二叉树。那么我们用递归的思想来解决这个问题。

#### 递归(自顶向下)

在这里,我们先用自顶向下的思路来去解决这个问题。

上面说了,要判断一个二叉树是否是平衡二叉树?要看所有子树是否都是平衡二叉树,那么这里需要比较每个节点左右子树的高度差绝对值,不能超过 1。

那么,首先考虑计算节点的高度 height,会有以下情况:

- 若当前节点为空节点,那么返回高度 0;

- 若当前节点为非空节点,那么这里返回左右子树中的最大高度 + 1。

然后,要考虑的是如何去判断是否平衡?情况如下:

- 先处理特殊情况,如果根节点为空,直接返回 True;

- 根节点非空,那么这里用先序遍历递归,对下面三种情况进行判断:

- 判断当前子树是否是平衡二叉树;

- 判断当前子树的左子树是否是平衡二叉树;

- 判断当前子树的右子树是否是平衡二叉树。

具体的代码见【代码实现 # 递归(自顶向下)】

#### 递归(自底向上)

在上面 **递归(自顶向下)** 的方法中,会产生大量重复计算,时间复杂度较高。

这里具体的做法如下:

- 设定终止条件:

- 越过叶子节点时,返回高度 0;

- 若左右子树任一高度为 -1 的情况下,代表左右子树不平衡,直接返回 -1。(这里左右子树高度由下面的左右子树高度差绝对值是否超过 1 决定)

- 如果当前节点左右子树的高度差的绝对值不超过 1 时,那么返回左右子树最大高度 +1;

- 如果当前节点左右子树的高度差的绝对值超过 1 时,返回 -1,表示子树不平衡。

具体的代码见【代码实现 # 递归(自底向上)】

## 代码实现

---

```python

# 递归(自顶向下)

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

def isBalanced(self, root: TreeNode) -> bool:

def depth(root):

"""求当前节点的深度

Args:

root: 节点

Returns:

返回节点深度

"""

# 节点为空,返回高度 0

if not root:

return 0

# 否则返回左右子树最大高度值 +1

return max(depth(root.left), depth(root.right)) + 1

# 根节点为空,直接返回 True

if not root:

return True

# 否则递归判断

# 1. 当前子树是否平衡

# 2. 当前子树左子树是否平衡

# 3. 当前子树右子树是否平衡

return abs(depth(root.left)-depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

# 递归(自底向上)

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

def isBalanced(self, root: TreeNode) -> bool:

def helper(root):

if not root:

return 0

left = helper(root.left)

# 当左右子树高度为 -1,表示不平衡返回 -1

if left == -1:

return -1

right = helper(root.right)

if right == -1:

return -1

# 判断左右子树高度差的绝对值是否不超过 1

return -1 if abs(left-right) > 1 else max(left, right) + 1

return helper(root) >= 0

```

## 实现结果

---

![实现结果 | 递归(自顶向下)](https://img-blog.csdnimg.cn/20200817175001945.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjkxOA==,size_16,color_FFFFFF,t_70#pic_center)

![实现结果 | 递归(自底向上)](https://img-blog.csdnimg.cn/20200817175704404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjkxOA==,size_16,color_FFFFFF,t_70#pic_center)

## 欢迎关注

---

公众号 【[书所集录](https://i.loli.net/2020/07/09/sNEGeV8g6fmW5Ub.jpg)】

相关文章:

「欧拉定理」学习笔记(费马小定理)

欧拉定理&#xff1a;对于互质的两个正整数$a, n$&#xff0c;满足$a^{φ(n)} ≡ 1\ (mod\ n)$ 证明&#xff1a; 设集合$S$包含所有$n$以内与$n$互质的数&#xff0c;共有$φ(n)$个&#xff1a;$$S \{ x_1, x_2, ..., x_{φ(n)} \} $$ 再设集合$T$&#xff1a;$$T \{ a * x…

Python将MySQL表数据写入excel

背景&#xff1a;将mysql表查询结果写入excel。 1.使用sqlyog工具将查询结果导出到Excel.xml中&#xff0c;用excel打开发现&#xff1a;因为text字段中有回车换行操作&#xff0c;显示结果行是乱的。 2.用mysql -uadmin -p -h -P -NBe"select * from tb;" >>a…

nacos动态配置数据源_Jasper 怎么配置动态数据源

Jasper 本身是不支持动态数据源的&#xff0c;能用的解决方式是通过 api 自定义数据源&#xff0c;实际操作就是根据条件判断后动态设定 jdbc 的 url、用户名及密码等连接属性。比如&#xff1a;String userName userDetails.getUsername();// obtain a connection based on t…

Linux命令之top

top –hv | -abcHimMsS –d delay –n iterations –p pid [, pid …] top程序提供运行系统的动态实时视图&#xff0c;它可以显示系统概要信息以及当前由Linux内核当前管理的任务列表。所示的系统概要信息的类型以及为任务显示的信息的类型、顺序和大小都是用户可配置的&#…

seal report mysql_Seal Report开放数据库报表工具(.Net)

概述&#xff1a;开放数据库报表工具(.Net)简介&#xff1a;Seal-Report提供了一个完整的框架&#xff0c;用于从任何数据库生成日常报告和仪表板。Seal-Report是Microsoft .NET Framework完全用C&#xff03;编写的开源工具。Seal Report算是报表工具中比较好用的一个&#xf…

注册亚马逊云服务

要英文填写还要字符限制&#xff0c;好严格 转载于:https://www.cnblogs.com/ZHONGZHENHUA/p/6249805.html

行波iq调制器_高速InP基半导体电光调制器行波电极结构研究

【1】Winzer P J, Essiambre R J. Advanced modulation formats for high-capacity optical transport networks[J].Lightwave Technol., 2006, 24(12):4711-4728.【2】Dagli N.High-speed photonics device[M]. Taylor & Francis, 2007.【3】Zhang L,Sinsky J, Thourhout …

PIXI 下落文字消除(3)

图片示例&#xff0c;简陋的图&#xff0c;记录下落过程&#xff0c; 1、创建应用实例并添加到DOM元素上。 &#xff08;会看到一个黑色画布&#xff0c;没有任何元素&#xff0c;接下来会在画布上创建文字&#xff09; 2、创建 TextStyle 用来设置要显示字体样式 3、随机产生…

python魔术方法call_php魔术方法__call

__call是魔术方法中的一个&#xff0c;当程序调用到当前类中未声明或没权限调用的方法时&#xff0c;就会调用__call方法class test{public function emptyFunc(){$getArgs func_get_args();$funcName $getArgs[0];//$params array_slice($getArgs, 1);//var_dump($params);…

app启动时间命令

app启动&#xff1a; 冷启动和热启动 冷启动方式&#xff1a; adb shell am start -W -n package/activity 停止app命令&#xff1a; adb shell am force-stop package 热启动命令和冷启动命令一样 停止命令&#xff1a; adb shell input keyevent 3 查看package/activity命令&…

华为手机媒体音量自动静音_华为手机的音量键还可以这么用,涨见识!

身边很多朋友都是用的是华为手机&#xff0c;我就纳闷了&#xff0c;华为手机真的有那么好用吗&#xff1f;听朋友跟我细细说了一番&#xff0c;我被说动了&#xff0c;准备也去换一个华为手机&#xff0c;就冲它的音量键有那多妙用&#xff0c;我也不能错过一款华为手机&#…

Mui.ajax请求服务器正确返回json数据格式

ajax&#xff1a; mui.ajax(http://server-name/login.php,{data:{username:username,password:password},dataType:json,//服务器返回json格式数据type:post,//HTTP请求类型timeout:10000,//超时时间设置为10秒&#xff1b;success:function(data){//服务器返回响应&#xff0…

day1作业(格式化输出)

练习&#xff1a;用户输入姓名、年龄、工作、爱好 &#xff0c;然后打印成以下格式------------ info of Egon -----------Name : EgonAge : 22Sex : maleJob : Teacher ------------- end -----------------完成情况&#xff1a;in_nameinput(请输入您的姓名&#xff1…

rust 官服指令_RUST 命令大全(包括服务器指令)

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼RUST MOD(以下在聊天框内输入)基本命令/share playername 【shares your doors with a player(共享你的门给一个玩家)】/unshare playername 【unshares your doors with a player(解除对一个玩家的门共享)】/help 【Shows command…

postgresql存图片字段类型_PostgreSQL 入门 | Linux 中国

安装、设置、创建和开始使用 PostgreSQL 数据库。-- Greg Pittman每个人或许都有需要在数据库中保存的东西。即使你执着于使用纸质文件或电子文件&#xff0c;它们也会变得很麻烦。纸质文档可能会丢失或混乱&#xff0c;你需要访问的电子信息可能会隐藏在段落和页面的深处。在我…

关于ES6中Promise的应用-顺序合并Promise,并将返回结果以数组的形式输出

1.Promise 基础知识梳理 创建一个Promise实例 const promise new Promise(function(resolve, reject) {if (success){resolve(value);} else {reject(error);} }); Promise构造函数接受一个函数作为参数&#xff0c;该函数的两个参数分别是resolve和reject。它们是两个函数&am…

Java计算两个字符串日期之间的天数差

Java计算两个字符串日期之间的天数差 调用方法&#xff1a; public static void main(String[] args) throws ParseException {String a "2017-12-01"; // 时间字符串String b "2017-12-31";Long between_dayInteger between_days(a, b);System.out.pri…

java file_Java IO: File

原文链接 作者: Jakob Jenkov 译者: 李璟(jlee381344197gmail.com)Java IO API中的FIle类可以让你访问底层文件系统&#xff0c;通过File类&#xff0c;你可以做到以下几点&#xff1a;检测文件是否存在读取文件长度重命名或移动文件删除文件检测某个路径是文件还是目录读取目录…

数学建模优化模型简单例题_数学建模之优化模型:存储模型

点击上方「蓝字」关注我们最近&#xff0c;为申报市级精品课程&#xff0c;我为我校“数学建模与科学计算”课程录制了讲课视频&#xff0c;下面是3.1节优化模型的第一个例子&#xff1a;存储模型。敬请大家批评指正&#xff01;优化模型是数学建模里比较简单、但也非常常用的建…

shiro异常类型

<!-- 身份认证异常 --> <!-- 身份令牌异常&#xff0c;不支持的身份令牌 --> org.apache.shiro.authc.pam.UnsupportedTokenException <!-- 未知账户/没找到帐号,登录失败 --> org.apache.shiro.authc.UnknownAccountException <!-- 帐号锁定 --&…

生产环境下Centos 6.5优化配置 (装载)

本文 centos 6.5 优化 的项有18处: 1、centos6.5最小化安装后启动网卡 2、ifconfig查询IP进行SSH链接 3、更新系统源并且升级系统 4、系统时间更新和设定定时任 5、修改ip地址、网关、主机名、DNS 6、关闭selinux&#xff0c;清空iptables 7、创建普通用户并进行sudo授权管理 8…

java this final_Java this、final等关键字总结

this关键字this引用对象自身。它也可以在构造方法内部用于调用同一个类的其他构造方法。隐藏的静态变量可以通过”类.静态变量”来引用&#xff0c;而隐藏的实例变量就需要使用”this.实例变量”来引用。调用一个重载的构造方法this引用是必须的。this是个隐式参数&#xff0c;…

档案盒正面标签制作_2020昆明大学档案盒价格价格行情

2020昆明大学档案盒价格价格行情背景技术档案盒是企业、单位部门或财务部门整理和装订储存文件的不可缺少的办公用具&#xff0c;主要是对档案材料、财务凭证等进行收集、查找等。目前需要查找档案时需要将所有的档案材料取出&#xff0c;然后一一查找&#xff0c;工作效率低&a…

jQuery效果:隐藏、显示、切换、滑动、淡入淡出、动画

jQuery效果 隐藏、显示、切换、滑动、淡入淡出、以及动画1、隐藏与显示(改变&#xff1a;display&#xff1a;none;) hide()——隐藏 show()——显示toggle()方法&#xff1a;可以使用它来切换hide()与show()方法 eg1&#xff1a;显示 <style type"text/css"> …

《C和指针》pdf

下载地址&#xff1a;网盘下载 本书提供与C语言编程相关的全面资源和深入讨论。本书通过对指针的基础知识和高级特性的探讨&#xff0c;帮助程序员把指针的强大功能融入到自己的程序中去。 全书共18章&#xff0c;覆盖了数据、语句、操作符和表达式、指针、函数、数组、字符串、…

linux 用户java_linux之用户管理

linux是多用户多任务的系统。每个用户都有一个账户。账户不能重复&#xff0c;密码允许重复。成功验证&#xff0c;则进入系统和自己的主目录(也就是家目录里面)。用户-----用户账号&#xff0c;添加、删除、修改以及用户密码管理。用户组------用户组管理。注意三个文件/etc/p…

k均值聚类图像分割matlab代码_用K均值聚类法为人类拍摄的首张黑洞照片进行分割...

众所周知&#xff0c;人类最近拍摄了首张黑洞照片。网友们纷纷表示&#xff0c;这明明就是一个甜甜圈嘛&#xff01;以前以为黑洞是这个世界上最最高冷的存在&#xff0c;而此刻突然现出真身&#xff0c;形象却是如此的人畜无害&#xff01;不但如此&#xff0c;还勾起了网友的…

else 策略模式去掉if_设计模式(三)——简单的状态模式代替if-else

博主将会针对Java面试题写一组文章&#xff0c;包括J2ee&#xff0c;SQL&#xff0c;主流Web框架&#xff0c;中间件等面试过程中面试官经常问的问题&#xff0c;欢迎大家关注。一起学习&#xff0c;一起成长。前言大多数开发人员现在还在使用if else的过程结构&#xff0c;曾看…

bzoj 3598 [ Scoi 2014 ] 方伯伯的商场之旅 ——数位DP

题目&#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id3598 数位DP...东看西看&#xff1a;http://www.cnblogs.com/Artanis/p/3751644.html https://www.cnblogs.com/MashiroSky/p/6399095.html 好巧妙的思路啊&#xff01;这样统计的东西就变得很简单了&#x…

OSI模型第四层传输层--TCP协议

1.传输层2个协议tcp和udp 2.tcp的可靠性&#xff08;挂号信&#xff09;。 面向链接的:类似寄挂号信&#xff0c;对方收到了并且能够确认。所以也是可靠的传输。 最大报文传输&#xff1a;两端可以协商传输报文大小。&#xff08;协商一个报文的大小&#xff09; 传输确认机制&…