leetcode_110. 平衡二叉树
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3 ...
目录
一、题目内容
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
二、解题思路
记录左右子树的深度,叶节点深度为1,如果累计高度差大于1,则返回小于0的数(这里取-1)。
若两棵子树有一个或两个返回负值,则其父亲也为负。
最后检验root的高度,小于0则False,大于等于0为True。
三、代码
# 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 dfs(root):
if root is None:
return 0
lh = dfs(root.left)
rh = dfs(root.right)
if lh >= 0 and rh >= 0 and abs(lh - rh) <= 1:
return 1 + max(lh, rh)
else:
return -1
return dfs(root) >= 0
if __name__ == '__main__':
a = TreeNode(3)
a.left = TreeNode(9)
a.right = TreeNode(20)
a.right.left = TreeNode(15)
a.right.right = TreeNode(7)
s = Solution()
ans = s.isBalanced(a)
print(ans)
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/108708823
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)