重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这期内容当中小编将会给大家带来有关python中的平衡二叉树该怎么理解,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
为自流井等地区用户提供了全套网页设计制作服务,及自流井网站建设行业解决方案。主营业务为成都网站设计、做网站、自流井网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树。
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
节点=>深度
字典中; 然后再遍历一遍节点, 针对每个节点, 判断它左右子节点的深度是否满足要求, 所有节点都满足的话才说明平衡. 但是这种方案需要遍历两边节点, 效率不太高, 如何一次性遍历得出结果呢?class Solution:
def isBalanced(self, root: TreeNode) -> bool:
# 递归, 边求深度边判断, 返回深度, 全局变量标记当前是否平衡
balance = True
def getDepth(node):
nonlocal balance
if not node or not balance:
# 递归出口: 如果节点为空或者不平衡, 返回0, 无需继续递归了
return 0
ldepth = getDepth(node.left)
rdepth = getDepth(node.right)
if abs(ldepth - rdepth) > 1:
# 不平衡, 全局变量设为false
balance = False
# 返回当前节点自身的深度
return max(ldepth, rdepth) + 1
getDepth(root)
return balance
上述就是小编为大家分享的python中的平衡二叉树该怎么理解了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联行业资讯频道。