如何用Python实现验证二叉树是否为最小堆的函数？

有没有内置方法直接检查？ #

Python标准库的heapq模块里没有直接判断二叉树是否为最小堆的方法。你给出的代码存在几个问题：

• heapify函数没有返回值，执行后会直接修改原列表为堆结构，返回的是None，所以if heapify(tree)这个判断永远为False
• 外层的while len(tree) > 1循环完全没必要，第一次循环就会直接返回结果
• 逻辑错误：heapify是转换堆，不是检查堆，哪怕输入不是堆，它也会把列表改成堆结构，没法用来判断原结构是否是堆

正确的实现方式 #

情况1：二叉树用列表紧凑存储（完全二叉树形式） #

这种存储方式是堆的标准存储格式：索引为i的节点，左孩子是2*i+1，右孩子是2*i+2。最小堆的核心规则是每个父节点的值小于等于其左右孩子的值，我们只需要遍历所有非叶子节点验证这个规则即可：

def is_min_heap(tree):
    n = len(tree)
    # 遍历所有非叶子节点（最后一个非叶子节点索引为 n//2 -1）
    for i in range(n // 2 - 1, -1, -1):
        # 检查左孩子是否满足最小堆条件
        if tree[i] > tree[2 * i + 1]:
            return False
        # 检查右孩子（如果存在）
        right_child_idx = 2 * i + 2
        if right_child_idx < n and tree[i] > tree[right_child_idx]:
            return False
    return True

情况2：二叉树用节点类表示 #

如果是用自定义节点类（带val、left、right属性）的二叉树，要成为最小堆需要满足两个条件：

1. 是完全二叉树（除了最后一层，其他层节点都满，最后一层节点靠左排列）
2. 每个父节点的值小于等于其左右孩子的值

实现代码如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_min_heap_tree(root):
    if not root:
        return True
    
    # 第一步：检查是否为完全二叉树
    queue = [root]
    # 标记是否已经出现过空节点
    encountered_empty = False
    
    while queue:
        node = queue.pop(0)
        if not node:
            encountered_empty = True
        else:
            # 如果之前已经出现过空节点，现在又有非空节点，说明不是完全二叉树
            if encountered_empty:
                return False
            queue.append(node.left)
            queue.append(node.right)
    
    # 第二步：检查堆的性质
    def check_heap_property(node):
        if not node:
            return True
        # 检查左孩子
        if node.left and node.val > node.left.val:
            return False
        # 检查右孩子
        if node.right and node.val > node.right.val:
            return False
        # 递归验证左右子树
        return check_heap_property(node.left) and check_heap_property(node.right)
    
    return check_heap_property(root)

内容的提问来源于stack exchange，提问作者Gilbert Mutai