判断是否是平衡二叉树

题目：输入一个二叉树，判断其是否是平衡二叉树。平衡二叉树的定义是任何节点的左右子树高度差都不超过1的二叉树。

解法一：编写一个求解节点深度的方法，然后从根节点开始判断其左右节点的深度相差是否大于1.

class BinTree(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    
    def get_depth(self, node):
        if not node:
            return 0
        
        left = self.get_depth(node.left)
        right = self.get_depth(node.right)
        return max(right, left) + 1
    
    def is_balance(self, proot):
        if not proot:
            return True
        
        left = self.get_depth(proot.left)
        right = self.get_depth(proot.right)
        
        if abs(left - right) > 1:
            return False
        
        return BinTree.is_balance(proot.left) and BinTree.is_balance(proot.right)

上述代码固然简洁，但我们也不难发现一个节点会被重复遍历多次，其时间效率不高。上述方法重复遍历的原因是从顶向下求解深度，如果我们从底向上判断并记录对应深度，我们就可以一边遍历一边判断，无需重复遍历。
考虑到节点为空时，他的深度为0，非空时，其深度大于0，当发现有一个节点的左右子树不平衡时，我们可以用一个小于0的数字来代表不平衡。

class BinTree(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    
    def isBalance(self, proot):
        def max_depth(root):
            if not root:
                return 0

            left = max_depth(proot.left)
            right = max_depth(proot.right)

            if left == -1 or right == -1 or abs(right - left) > 1:
                return -1

            return 1 + max(left, right)
    
        return max_depth(proot) != -1