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

可视化图解算法33:判断是不是平衡二叉树

1. 题目

描述

输入一棵节点数为 n 的二叉树,判断该二叉树是否是平衡二叉树。

在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树

平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

样例解释:

样例二叉树如图,为一颗平衡二叉树

注:我们约定空树是平衡二叉树。

数据范围:n≤100,树上节点的val值满足 0 ≤n≤1000

要求:空间复杂度O(1),时间复杂度 O(n)

输入描述:

输入一棵二叉树的根节点

返回值描述:

输出一个布尔类型的值

示例1

输入:

{1,2,3,4,5,6,7}

返回值:

true

示例2

输入:

{}

返回值:

true

2. 解题思路

先来看平衡二叉树的性质:

平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

因此可以借助二叉树的高度来判断是否为平衡二叉树。整体思路为:先计算左右子树的高度,再比较左右子树的高度差(如果高度差大于1,则不是平衡二叉树)。

①对每一个节点的左右子树进行比较;②如果左子树不是平衡二叉树,就没有必要对右子树进行是否平衡的判断;③采用递归的方式对左右子树进行判断。

由于要采用递归来实现平衡二叉树的判断,因此需要验证是否满足递归的两个条件:

可以看出,求解二叉树平衡性的判断满足递归的两个条件,因此可以采用递归的方法来求解。由于平衡性的判断依赖于二叉树的高度,二叉树的高度求解参考前序文章《可视化图解算法25:二叉树的最大深度(高度)》,二叉树高度求解对应的递推公式如下:

接下来就可以依据二叉树的高度进行平衡性的判断,先求解二叉树的左右子树的高度,再判断左右子树高度差是否超过1,如果超过1则不是平衡二叉树。

如果文字描述的不太清楚,你可以参考视频的详细讲解。

  • Python编码:哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372113

  • Java编码:数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367352

  • Golang编码:哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364777

3. 编码实现

核心代码如下:

/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类* @return bool布尔型
*/
func IsBalanced_Solution(pRoot *TreeNode) bool {// write code heretreeDepth(pRoot)return isBalanced
}var isBalanced = truefunc treeDepth(root *TreeNode) int {// 2. 递归终止条件if root == nil {return 0}// 1. 问题分解// 1.1 求解左子树的高度l := treeDepth(root.Left)// 1.2 求解右子树的高度r := treeDepth(root.Right)if math.Abs(float64(l-r)) > 1 {isBalanced = false // 不是平衡树,更改全局变量return -1          // 加一个标记-1,已经不可能是平衡树了(减少递归计算次数),直接返回}// 1.3 求解当前树的高度dep := math.Max(float64(l), float64(r)) + 1return int(dep)
}

具体完整代码你可以参考下面视频的详细讲解。

  • Python编码:哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372113

  • Java编码:数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367352

  • Golang编码:数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364777

4.小结

二叉树平衡性的判断,可以通过二叉树的高度来完成,即先求解二叉树的左右子树的高度,再判断左右子树高度差是否超过1,如果超过1则不是平衡二叉树。

《数据结构与算法》深度精讲课程正式上线啦!七大核心算法模块全解析:

  ✅   链表

  ✅   二叉树

  ✅   二分查找、排序

  ✅   堆、栈、队列

  ✅   回溯算法

  ✅   哈希算法

  ✅   动态规划

无论你是备战笔试面试、提升代码效率,还是突破技术瓶颈,这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡,与千名开发者共同进阶!

  • Python编码实现:数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss897667807

  • Java编码实现:数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss161443488

  • Golang编码实现:数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss63997

对于二叉树的相关算法,我们总结了一套【可视化+图解】方法,依据此方法来解决相关问题,算法变得易于理解,写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句:长风破浪会有时,直挂云帆济沧海。

http://www.xdnf.cn/news/4482.html

相关文章:

  • C++自动重连机制设计与实现指南
  • 融智学核心理论的数学化表达(之二)
  • Java中的Classpath 包含哪些目录?
  • 为什么800*800mm防静电地板“应用较少
  • 基于@ConfigurationProperties+@EnableConfigurationProperties的配置管理-笔记
  • Qt/C++面试【速通笔记七】—Qt中为什么new QWidget不需要手动调用delete?
  • 资产管理系统选型避坑:2025年核心技术趋势洞察
  • 求组合数【递推+快速幂+卢卡斯+线性筛】
  • AAAI2025论文整理-数字人驱动方向
  • spark 的流量统计案例
  • android-ndk开发(8): ndk 和 clang 版本对照表
  • 北京华锐视点邀您参与2025数字显示与元宇宙博览会【5月10-12日】
  • 浅谈Vue2 与 Vue3 的区别
  • 前端流行框架Vue3教程:13. 组件传递数据_Props
  • 学习Linux的第三天
  • 某振动分析系统的参数交叉核算
  • 解决 pnpm dev 运行报错的坎坷历程
  • 【第25节 性能指标计算】
  • 4.1框架应用
  • 系统架构师2025年论文《信息系统安全体系设计》
  • Xilinx DSP48E2 slice 一个周期能做几次float32浮点数乘法或者加法?如果是fix 32定点数呢?
  • “wsl --install -d Ubuntu-22.04”下载慢,中国地区离线安装 Ubuntu 22.04 WSL方法(亲测2025年5月6日)
  • python + whisper 读取蓝牙耳机, 转为文字
  • JavaScript 到命令和控制 (C2) 服务器恶意软件分析及防御
  • 三生原理是如何与狄利克雷定理兼容的?
  • 使用docker配置Mysql
  • 2021-10-29 C++被17或13整除最大10个数的和
  • 六六大顺--高精度+数学
  • 【QT】QT软件编译生成exe后,需要拷贝依赖库使用方法
  • 使用Windows+Linux实现mysql的主从复制