JZ79 判断是不是平衡二叉树

题目描述

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

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

样例解释：

样例二叉树如图，为一颗平衡二叉树
注：我们约定空树是平衡二叉树。

数据范围：n≤100n \le 100,树上节点的val值满足 0≤n≤10000 \le n \le 1000 要求：空间复杂度O(1)，时间复杂度 O(n)

解题思路

判断一个数是否为平衡二叉树：左子树的高度与右子树的高度差的绝对值小于等于1，同样左子树是平衡二叉树，右子树为平衡二叉树。

1. 求出以每个结点为根的树的深度，
2. 根据左右子树高度差绝对值小于等于1，就可以判断以每个结点为根的树是否满足定义。
3. 保证左右子树都是平衡二叉树

代码实现

from turtle import right
from typing import Tuple

from sympy import root


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
        if pRoot==None:
            return True
        
        # 递归求二叉树的深度
        def depth(root:TreeNode):
            if root==None:
                return 0
            ldep=depth(root.left)
            rdep=depth(root.right)
            return max(ldep,rdep)+1
        
        # 判断二叉树是否为平衡二叉树
        def judge(root:TreeNode):
            if root ==None:
                return True
            ldep=depth(root.left)   # 每一个左子树的深度
            rdep=depth(root.right)  # 每一个右子树的深度
            if abs(ldep-rdep)>1:    # 若左右子树差大于1 则不是平衡二叉树
                return False
            return judge(root.left) and judge(root.right)   # 递归保证所有的左右子树都是平衡二叉树

        return judge(pRoot)     # 调用