给定一个二叉树,判断它是否是高度平衡的二叉树。
示例:
Ture
False
首先做这道题目前要明白什么是平衡二叉树?平衡二叉树的定义是,对于二叉树的每一个节点,它的左子树和右子树的高度差不超过1。结合示例中的两个例子理解平衡二叉树的定义。
完整代码如下:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if self.get_height(root) != -1:
return True
else:
return False
def get_height(self, root: TreeNode) -> int:
# Base Case
if not root:
return 0
# 左
if (left_height := self.get_height(root.left)) == -1:
return -1
# 右
if (right_height := self.get_height(root.right)) == -1:
return -1
# 中
if abs(left_height - right_height) > 1:
return -1
else:
return 1 + max(left_height, right_height)
首先我们看一下代码的整体框架:
Solution类中包含两个方法:
- isBalanced:用于判断整棵树是否是平衡二叉树。
- get_height:用于计算一个节点的高度,同时判断该节点的子树是否平衡。
在isBalanced函数中,接收一个二叉树的根节点root作为输入。调用get_height方法来获取树的高度,如果get_height返回的结果不为-1,则表示树是平衡的,返回True;否则返回False。
get_height函数中如果当前节点为空,则返回0
# 左
if (left_height := self.get_height(root.left)) == -1:
return -1
# 右
if (right_height := self.get_height(root.right)) == -1:
return -1
分别利用递归计算左右子树的高度,通过递归调用get_height函数,然后将左子树高度存储在left_height中,如果left_height等于-1,说明左子树不平衡,返回-1。右子树同理。代码中的:=代表什么?:=是Python 3.8 引入的“海象运算符”(Walrus Operator)。它的作用是将表达式的值赋给一个变量,并返回这个值。这种语法允许你在一个表达式内部进行赋值,从而可以在一行代码中完成赋值和使用的操作。简单来讲就是为了代码简洁性,完整代码应该是这样的:
left_height = self.get_height(root.left)
if left_height == -1:
return -1
接着判断平衡性:
if abs(left_height - right_height) > 1:
return -1
else:
return 1 + max(left_height, right_height)
如果左右子树高度差大于1,那也是不平衡的,其余的返回节点高度。这里可能有疑问,为什么要返回节点高度?在isBalanced中只要不等于-1不就返回True了么,那我对于满足的只要不返回-1不就行了么?但你这是在递归,你在一层中随意返回一个不等于-1的值,那其余层递归内,怎么确定节点高度?所以还是得返回节点高度,是为了下一层或者上一层递归的正确性。
标签:right,return,get,self,height,二叉树,平衡,left From: https://blog.csdn.net/plutomty/article/details/141086611