Easy
给定二叉树，判断其是否为平衡树。
Solution：
什么是平衡树？
空树平衡，非空二叉树满足下面条件时为平衡：
- 左分支平衡
- 右分支平衡
- 左右分支树的高度差不大于1
此题最直接的想法是从根节点往下，比较每个节点的左右深度，如果每个节点都是平衡的那么整棵树就是平衡的，这个方法是top-bottom的办法，复杂度为O(N**2)。复杂度太高所以思考是否可以有简单一些的办法。
下面是Bottom-top的方法。从最底层的节点开始比较，一旦出现不平衡节点就返回负值，如果到最后都没有返回负值，则整棵树平衡。这个方法的复杂度为O(N)。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.dfs_height(root) != -1
def dfs_height(self, root):
if not root: return 0
left_height = self.dfs_height(root.left)
if left_height == -1: return -1
right_height = self.dfs_height(root.right)
if right_height == -1: return -1
if abs(left_height - right_height) > 1: return -1
return max(left_height, right_height) + 1
