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

算法刷题Day14:BM36 判断是不是平衡二叉树

题目链接

描述
输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

思路

递归遍历,返回左右子树高度。使用一个全局变量记录左右子树是否有相减超过1的情况。

代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def __init__(self) -> None:self.result = Truedef traverse(self, root):if root == None:return 0left_height = self.traverse(root.left) right_height = self.traverse(root.right)if abs(right_height - left_height)>1:self.result = Falsereturn max(left_height,right_height)+1 def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:# write code here# 返回当前树的高度。全局记录是否有高度差超过1的self.traverse(pRoot)return self.result

cool~ 5分钟ac了这道题!!!!

http://www.lryc.cn/news/500561.html

相关文章:

  • 【Golang】Go语言编程思想(六):Channel,第一节,介绍Channel
  • 【Flux.jl】 卷积神经网络
  • 大模型在辅导场景的深度应用,猿辅导素养课推出启发性“AI作文通”
  • 深入了解架构中常见的4种缓存模式及其实现
  • Hermes engine on React Native 0.72.5,function无法toString转成字符串
  • Spring Boot + MySQL 多线程查询与联表查询性能对比分析
  • Java 设计模式~工厂模式
  • OmicsTools生信环境全自动化安装配置教程,代做生信分析和辅导
  • 鸿蒙HarmonyOS应用开发 探索 HarmonyOS Next-从开发到实战掌握 HarmonyOS Next 的分布式能力
  • 二分模板题
  • 一篇文章掌握Git的基本原理与使用
  • 「Mac畅玩鸿蒙与硬件43」UI互动应用篇20 - 闪烁按钮效果
  • 朗新科技集团如何用云消息队列 RocketMQ 版“快、准、狠”破解业务难题?
  • 【Ubuntu】Ubuntu的Desktop(学习/用户使用)和Bit版本(工作)
  • cmake CMAKE_CURRENT_SOURCE_DIR和CMAKE_CURRENT_LIST_DIR的区别
  • 学会用VSCode debug
  • C语言专题之结构体的使用
  • python中的高阶函数
  • 学习笔记063——通过使用 aspose-words 将 Word 转 PDF 时,遇到的字体改变以及乱码问题
  • SpringBoot整合Mockito进行单元测试超全详细教程 JUnit断言 Mockito 单元测试
  • 【AI知识】过拟合、欠拟合和正则
  • MacOS编译webRTC源码小tip
  • Linux基础命令(三):文件压缩及解压缩命令
  • 目标跟踪算法:ByteTrack、卡尔曼滤波、匈牙利算法、高置信度检测目标、低置信度检测目标
  • [定昌linux系统]如何安装jdk8
  • 【Cadence32】PCB多层板电源、地平面层创建心得➕CM约束管理器Analyze分析显示设置➕“DP”报错DRC
  • 基于SpringBoot+Vue的新闻管理系统
  • 图的割点、割边(Tarjan算法)
  • 算法学习(十四)—— 二叉树的深度搜索(DFS)
  • 【vue2】封装自定义的日历组件(三)之基础添加月份的加减定位到最新月份的第一天