平衡二叉树

题目描述

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

思路

思路1：从上而下的判断。从根节点开始，判断是不是平衡二叉树。是的话再分别看左右的孩子。但是这样孩子节点会被重复计算，时间复杂度在。
具体在代码实现的时候，每到一个节点，就调用一次深度计算的方法，判断深度是否符合要求。然后递归的对子节点进行深度计算与判断。
思路2：从下向上的判断。和后序遍历的顺序一样，左右根。判断这个子树是不是平衡的，如果是，继续向上判断，最后判断根节点是不是平衡二叉树。这样的时间复杂度是N。
具体在代码实现的时候，会首先的递归的找到最底下的子树，然后从下向上的返回深度与当前子树是否匹配。一旦有不匹配的就结束了。

代码

这是从下至上版本，可以避免重复的计算同一个节点。
递归的搜索到最下面，然后开始计算深度并逐步返回，每一次会比较左右子树的深度是否符合要求，如果不符合就把类变量标为False。

class Solution:
    flag = True
    def IsBalanced_Solution(self, pRoot):
        self.helper(pRoot)
        return self.flag
    def helper(self,node):
        if node is None:
            return 0
        left = self.helper(node.left)+1
        right = self.helper(node.right)+1
        if abs(left - right)>1:
            self.flag = False
        return max(left,right)

这是从上至下版本，很好理解，但是复杂度高
从根节点开始，每一个节点，判断他的左右子树深度之差是否小于1，递归的看左右子树。

class Solution:
    flag = True
    def IsBalanced_Solution(self, pRoot):
        if pRoot is None:
            return True
        left = self.depth(pRoot.left)
        right = self.depth(pRoot.right)
        return abs(left - right)<2 and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
    def depth(self,node):
        if node is None:
            return 0
        left_depth = self.depth(node.left)
        right_depth = self.depth(node.right)
        return max(left_depth,right_depth) +1