判断是不是完全二叉树

判断一个给定的数据结构（通常是数组或链表）是否为完全二叉树，可以通过递归或迭代的方式来完成。完全二叉树的特点是除了最后一层外，每一层都是完全填充的，并且所有节点都尽可能地集中在左边。

对于数组表示的二叉树，我们可以从根节点开始，按层次遍历，对于每个节点，检查其左右孩子的状态。如果是叶子节点（没有孩子），那么只要剩余节点在下一层的位置上都有对应的空位，就可以继续向上；如果不是叶子节点，我们需要确认它的右孩子是否也存在。如果所有节点都能通过这种方式验证，那么该数据结构就是完全二叉树。

以下是一个简单的Python示例（假设数组是递增的顺序存储，INT_MAX表示无值）：

def is_complete_binary_tree(arr):
    n = len(arr)
    
    # 递归基情况：空数组和只包含一个元素的数组视为完全二叉树
    if n <= 1:
        return True
    
    # 查找数组中最右侧的有效节点
    rightmost_valid_index = find_rightmost_valid(arr)
    
    # 验证剩余部分是否为空或也是完全二叉树的形式
    if rightmost_valid_index * 2 < n and arr[rightmost_valid_index * 2] != None:  # 如果还有右孩子
        return is_complete_binary_tree(arr[leftmost_child(rightmost_valid_index):])
        
    return True  # 如果没有右孩子或已经到达叶子节点，说明它是完全二叉树


def find_rightmost_valid(arr):
    for i in range(len(arr) // 2, -1, -1):
        if arr[2 * i] != None:
            return i
    return 0  # 找不到有效节点，即数组只有一个元素或为空


def leftmost_child(parent_index):
    return 2 * parent_index  # 返回父节点的左孩子的索引


# 示例：
arr = [1, 2, 3, None, None, 6, 7]
print(is_complete_binary_tree(arr))  # 输出：True