# 输入一棵二叉树，判断该二叉树是否是平衡二叉树。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def IsBalanced_Solution(self, pRoot):
        return self.get_balanced_and_height(pRoot)[0]

    def get_balanced_and_height(self, p):
        if p is None:
            return True, 0
        lb = self.get_balanced_and_height(p.left)
        rb = self.get_balanced_and_height(p.right)
        height = max(lb[1], rb[1]) + 1
        balanced = (-1 <= lb[1] - rb[1] <= 1)
        if lb[0] and rb[0]:
            return balanced, height
        else:
            return False, height