题解 | #判断是不是平衡二叉树#
判断是不是平衡二叉树
http://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
自上而下
自上而下,遍历每一个节点,计算每个节点的左右子树高度,判断是否满足平衡二叉树的条件。
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# @param pRoot TreeNode类
# @return bool布尔型
#
class Solution:
def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
if not pRoot: return True
# 计算左右子树的深度
lDepth = self.depth(pRoot.left)
rDepth = self.depth(pRoot.right)
# 判断是否平衡
if abs(lDepth-rDepth) > 1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
# 计算树的高度
def depth(self,root):
if not root: return 0
return max(self.depth(root.left),self.depth(root.right))+1