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