Python递归实现判断二叉树是否为平衡二叉树
在Python中,可以使用以下递归代码判断二叉树是否为平衡二叉树:
class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def is_balanced(root): def helper(node): if not node: return 0 left_height = helper(node.left) if left_height == -1: return -1 right_height = helper(node.right) if right_height == -1: return -1 if abs(left_height - right_height) > 1: return -1 return max(left_height, right_height) + 1 return helper(root) != -1
其中,is_balanced
函数用于判断给定的二叉树root
是否为平衡二叉树,如果是,返回True
,否则返回False
。本函数内部调用helper
函数进行递归,计算出二叉树的每个节点的高度,并检查每个节点的左右子树高度差是否小于等于1。如果发现不平衡节点,则返回-1。最终,如果返回值不为-1,则说明该二叉树为平衡二叉树,否则不是。
相关文章