平衡二叉树与完全二叉树的判断

平衡二叉树（AVL树）和完全二叉树是两种重要的二叉树结构，它们各自具有独特的性质和用途。在实际应用中，我们需要判断一棵二叉树是否为平衡二叉树或完全二叉树。下面将分别介绍这两种二叉树的判断方法。

一、平衡二叉树的判断

平衡二叉树的定义是：一棵高度平衡的二叉树，其中任意节点的左子树和右子树的高度差不超过1。因此，我们可以通过递归遍历每个节点，并比较其左右子树的高度来判断一棵二叉树是否为平衡二叉树。具体实现如下：

def is_balanced(root):
    def height(node):
        if not node:
            return 0
        return max(height(node.left), height(node.right)) + 1
    if not root:
        return True
    return abs(height(root.left) - height(root.right)) <= 1 and is_balanced(root.left) and is_balanced(root.right)

在上述代码中，我们定义了一个内部函数height()来计算节点的高度。然后，在is_balanced()函数中，我们首先检查根节点是否存在，如果存在则计算左右子树的高度差，并检查是否满足平衡条件。最后，递归地检查左子树和右子树是否平衡。

二、完全二叉树的判断

完全二叉树的定义是：除了最后一层外，其他层的节点数达到最大，且最后一层的节点尽可能集中在左侧。我们可以使用深度优先搜索（DFS）遍历树的每个节点，并记录每个节点的层数。如果存在某个节点的层数与其父节点的层数相差超过1，则该树不是完全二叉树。具体实现如下：

def is_complete_binary_tree(root):
    def dfs(node, level):
        if not node:
            return True
        if level > 0 and (not dfs(node.left, level+1) or not dfs(node.right, level+1)):
            return False
        return node.left is None and node.right is None or level == 0
    return dfs(root, 0)

在上述代码中，我们定义了一个内部函数dfs()来进行深度优先搜索。在搜索过程中，我们记录每个节点的层数，并检查其左右子节点是否满足完全二叉树的定义。最后，返回根节点的搜索结果。

总结：平衡二叉树和完全二叉树是两种重要的二叉树结构，它们的判断方法各有不同。通过递归遍历每个节点并比较其左右子树的高度，我们可以判断一棵二叉树是否为平衡二叉树；通过深度优先搜索遍历每个节点并记录其层数，我们可以判断一棵二叉树是否为完全二叉树。在实际应用中，根据具体需求选择合适的判断方法，有助于更好地利用这两种二叉树的性质和用途。