Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

The same question appears on <Cracking> too (p86 4.1)

The key points to this problem is:

a.  check whether the current tree is balanced 
     i.e., |height(left sub tree) - height(right sub tree)| <= 1

b. check whether the left sub tree and right sub tree of the current tree is balanced
    It could be the case that even though the left, right height of the current tree differs no more 
    than one, the two trees are not balanced by themselves. e.g. the left sub tree could only 
    have left child and is an array...>__<

c. what is the height of the current tree ?
    height of the current tree is the maximum height of left and right sub tree + 1
    (even by wording, it is recursive in nature haha)

Something worth noticing:

a. since there are recursions in the process, it could lead to duplicates recursion. 
     notice that when you are calculating the height of the current tree, you actually already
     calculate the height of its left and right sub trees.  Use a DP :)

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

class Solution:
    # @param root, a tree node
    # @return a boolean
    def __init__(self):
        self.dp = {}

    def height(self, root):
        if root is None:
            return 0
        else:
            lh, rh = self.height(root.left), self.height(root.right)
            rh = max(lh, rh) + 1
            self.dp[root.left], self.dp[root.right] =lh, rh
        return h

    def isBalanced(self, root):
        if root is None:
            return True
        else:
            # this checks 1.whether is current tree is balanced; 2. whether its two sub trees are balanced
            return abs(self.height(root.left)-self.height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)