本文共 1096 字,大约阅读时间需要 3 分钟。
1.问题描述:
给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。
2.样例:
给出二叉树 A={3,9,20,#,#,15,7}
, B={3,#,20,15,7}
A) 3 B) 3 / \ \ 9 20 20 / \ / \ 15 7 15 7
二叉树A是高度平衡的二叉树,但是B不是。
3.代码:
"""Definition of TreeNode:class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, None"""class Solution: """ @param: root: The root of binary tree. @return: True if this Binary tree is Balanced, or false. """ def isBalanced(self, root): # write your code here if root is None: return True a=self.treeHeight(root.left) b=self.treeHeight(root.right) if abs(a-b)>1: return False else: return self.isBalanced(root.left) and self.isBalanced(root.right) def treeHeight(self,root): if root is None: return 0 else: lheight=self.treeHeight(root.left) rheight=self.treeHeight(root.right) return max(lheight,rheight)+1
转载地址:http://qauii.baihongyu.com/