Python递归实现判断二叉树是否为平衡二叉树

2023-04-15 00:00:00 平衡 二叉树 递归

在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,则说明该二叉树为平衡二叉树,否则不是。

相关文章