题解 | 判断二叉树是否为平衡二叉树

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isBalanced(self , root ):
        # write code here
        #判空，空则是平衡二叉树
        if not root :
                return True
        def maxHeight(r):
            #向下遍历到空结点，其高度为0
            if not r :
                return 0
            #计算左右子树的高度
            l_height = maxHeight(r.left)
            r_height = maxHeight(r.right)
            #如果结点的左右子树存在不平衡的子结点，则其直接返回-1
            if l_height == -1 or r_height == -1:
                return -1
            #子树都是平衡的，则计算该结点高度
            height = max(l_height,r_height)+1
            #判断该结点是否平衡，否则将高度置为-1
            if abs(l_height-r_height) > 1 :
                height = -1
            return height
        h = maxHeight(root)
        if h > 0:
            return True
        return False