剑指offer——python【第39题】平衡二叉树
2024-08-27 04:13:59
题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
解题思路
平衡二叉树首先是二叉搜索树,且它每个节点的左子树和右子树高度差至多等于1;只要从根节点,依次递归判断每个节点是否满足如上条件即可;那么可以首先构造一个求任意节点树深的函数TreeDepth,然后取左右子树的深度差的绝对值,判断是否大于1;然后递归判断左子树和右子树的每个节点,如果都小于等于1的话,则为平衡二叉树
代码
class Solution:
def TreeDepth(self,pRoot):
if pRoot is None:
return 0
lDepth = self.TreeDepth(pRoot.left)
rDepth = self.TreeDepth(pRoot.right)
return max(lDepth,rDepth)+1 def IsBalanced_Solution(self, pRoot):
# write code here
if pRoot is None:
return True
right = self.TreeDepth(pRoot.right)
left = self.TreeDepth(pRoot.left)
if abs(right-left)>1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
最新文章
- Java中this、super用法
- Servlet的response输出到页面时乱码的解决方法
- 函数fil_io
- Reids配置文件redis.conf中文详解
- PHP、Java、C#实现URI参数签名算法,确保应用与REST服务器之间的安全通信,防止Secret Key盗用、数据篡改等恶意攻击行为
- JavaScript实现弹框
- WPF与混淆器
- maven下配置pom.xml
- java的Xmx是设置什么的?
- Codeforces Round #485 (Div. 2) F. AND Graph
- 【译】参考手册-React组件
- Java——scoket通讯
- 百度编辑器ueditor 光标位置的坐标
- C++基础算法学习——猜假币
- wFuzz使用帮助
- kafka系列七、kafka核心配置
- 洛谷P1433 吃奶酪【dfs】【剪枝】
- Python str() 函数
- 心情烦闷annoying,贴几个图!唉!annoying
- Torch实现ReQU,和梯度验证
热门文章
- Correction suggestions
- Resources (being shared)
- 第30月第3天 iOS图标icon自动生成和自定义尺寸
- Codeforces Round #501 (Div. 3) D. Walking Between Houses
- Accoridion折叠面板
- java -jar参数携带问题
- git知识总结-1.git基础之基本术语
- GitHub界面初识
- iOS UIPrintInteractionController在iPad的 iOS10 和 11上的奇怪bug
- vue 父子之间通信及非父子之间通信