要确定一个二叉树是否平衡,可以使用以下方法:
以下是一个简单的Python代码实现:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
return max(height(root.left), height(root.right)) + 1
def is_balanced(root):
if not root:
return True
left_height = height(root.left)
right_height = height(root.right)
if abs(left_height - right_height) > 1:
return False
return is_balanced(root.left) and is_balanced(root.right)
在这个代码中,我们定义了一个TreeNode
类来表示二叉树的节点,并实现了height
和is_balanced
两个函数。height
函数用于计算二叉树的高度,而is_balanced
函数则用于检查二叉树是否平衡。
需要注意的是,这个算法的时间复杂度为O(n^2),因为我们需要计算每个节点的高度。如果需要更高效的算法,可以考虑使用后序遍历的方式来计算二叉树的高度,并在遍历过程中检查每个节点的左右子树的高度差。
领取专属 10元无门槛券
手把手带您无忧上云