算法刷题Day14:BM36 判断是不是平衡二叉树

题目链接

描述
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

思路

递归遍历，返回左右子树高度。使用一个全局变量记录左右子树是否有相减超过1的情况。

代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def __init__(self) -> None:self.result = Truedef traverse(self, root):if root == None:return 0left_height = self.traverse(root.left) right_height = self.traverse(root.right)if abs(right_height - left_height)>1:self.result = Falsereturn max(left_height,right_height)+1 def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:# write code here# 返回当前树的高度。全局记录是否有高度差超过1的self.traverse(pRoot)return self.result

cool~ 5分钟ac了这道题！！！！