题解 | #判断是不是平衡二叉树#

判断是不是平衡二叉树：

• 先定义一个深度优先遍历，来计算某个子树的高度
• 进行层序遍历，判断以每个节点为根节点的二叉树的左右子树高度差是否大于1

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        # 平衡二叉树的左右子树高度差不超过1
        if not pRoot:
            return True
        # 递归计算子树的高度
        def dfs(root):
            if not root:
                return 0
            return max([dfs(root.left),dfs(root.right)])+1
        
        node = list()
        node.append(pRoot)
        while node:
            temp = list()
            while node:
                node_temp = node.pop()
                print(dfs(node_temp.left))
                print(dfs(node_temp.right))
                if abs(dfs(node_temp.left) - dfs(node_temp.right)) > 1:
                    return False
                if node_temp.left:
                    temp.append(node_temp.left)
                if node_temp.right:
                    temp.append(node_temp.right)
            node = temp
        return True