题解 | #平衡二叉树#python 解法

先求高度， 再判断平衡。 我都是用的递归做， 感觉这题可以作为中等

class Solution:
    flag = True
    def IsBalanced_Solution(self, pRoot):
        dict_h = {}
        dict_h[None] = 0

        def height(root):
            if (root == None):
                return 0
            # 如果dict_h [root]存在， 直接取。
            if ((root) in dict_h):
                return dict_h[root]
            else:
                # 不存在, 重新计算
                # if(dict_h.has_key(root.left)):
                if ((root.left) in dict_h):
                    height_left = dict_h[root.left]
                else:
                    height_left = height(root.left)
                # if(dict_h.has_key(root.right)):
                if ((root.right) in dict_h):
                    height_right = dict_h[root.right]
                else:
                    height_right = height(root.right)

                dict_h[root] = max(height_left + 1, height_right + 1)
                return dict_h[root]

        # 假设有height字典

        def dfs(root):
            if (root == None):
                return
            # dict_h[None]
            # print("root.left, dict_h[root.left], root.right, dict_h[root.right]", root.left.val if root.left!=None else root.left, dict_h[root.left], root.right.val if root.right!=None else root.right, dict_h[root.right])
            # print("root.left, dict_h[root.left], root.right, dict_h[root.right]",  dict_h[root.left],  dict_h[root.right], abs(dict_h[root.left] - dict_h[root.right]))
            if (abs(dict_h[root.left] - dict_h[root.right]) <= 1):
                dfs(root.left)
                dfs(root.right)
            #     这里就应该结束。
            else:
                self.flag=False
                return
            # return True

        # write code here
        # 先求高度
        height(pRoot)
        # print("height(root.left)", dict_h[pRoot.left])
        # print("height(root.left)", dict_h[pRoot.left.left])
        # print("height(root.left)", dict_h[pRoot.left.right])
        if(pRoot==None):
            return True
        else:
            dfs(pRoot)
            return self.flag