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

判断是不是平衡二叉树

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

思路：用递归，如果当前节点的左右层数超过1，则不是平衡二叉树，如果没有超过1，则判断左右子树是否为平衡二叉树,如果左右子树都为平衡二叉树则改数为平衡二叉树

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    def countLevel(self,tree,n):
        if tree == None:
            return n
        else :
            return max(self.countLevel(tree.left, n+1), self.countLevel(tree.right, n+1))
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        # write code here
        if pRoot == None:
            return True
        if abs(self.countLevel(pRoot.left,0) - self.countLevel(pRoot.right,0)) > 1:
            return False
        else:
            return (self.IsBalanced_Solution(pRoot.left) & self.IsBalanced_Solution(pRoot.right))