帝国cms 网站迁移错版,福州做网站的公司,微电影分享网站织梦整站源码,做1个响应式设计网站好题目链接 描述 输入一棵节点数为 n 二叉树#xff0c;判断该二叉树是否是平衡二叉树。 在这里#xff0c;我们只需要考虑其平衡性#xff0c;不需要考虑其是不是排序二叉树 平衡二叉树#xff08;Balanced Binary Tree#xff09;#xff0c;具有以下性质#xff1a;它是…题目链接 描述 输入一棵节点数为 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.resultcool~ 5分钟ac了这道题
