判断以某节点为根的二叉树是否为最大堆

Question

我正在尝试判断一个以某个节点为根的二叉树是否是一个最大堆。为此，我遵循了最大堆的性质规则，具体如下：

最大堆：

所有节点的值都要大于或等于它的每一个子节点的值。

我的实现思路：

1. 如果传入的节点没有左子节点和右子节点，那就返回真（True）。
2. 否则，如果这个节点的值大于左子节点和右子节点的值，那么就分别对左子节点和右子节点再次调用这个函数。
3. 如果不满足上述条件，就返回假（False）。

我的代码：

class BTNode:
    '''A generic binary tree node.'''

    def __init__(self, v):
        '''(BTNode, int) -> NoneType

        Initialize a new BTNode with value v.

        '''
        self.value = v
        self.left = None
        self.right = None


def is_max_heap(node):
    '''(BTNode) -> bool

    Return True iff the binary tree rooted at node is a max-heap
    Precondition: the tree is complete.

    '''
    if node.left and node.right is None:
        return True
    else:
        if node.value > node.left.value and node.value > node.right.value:
            return is_max_heap(node.left) and is_max_heap(node.right)
        else:
            return False


if __name__ == '__main__':
    l1 = BTNode(7)
    l2 = BTNode(6)
    l3 = BTNode(8)
    l1.left = l2
    l1.right = l3
    print(is_max_heap(l1))

在 if __name__ == '__main__': 下面，我创建了三个节点，值分别是7、6和8。第一个节点有左子节点和右子节点。所以这棵树的样子是这样的：

   7
 /   \
6     8

这个树不满足最大堆的性质，所以应该返回假（False）。然而运行我的代码却返回真（True），我搞不清楚哪里出了问题。如果有人能帮我，那将非常感谢。

Answer 1

你没有考虑到只有 一个 子节点的情况。确保你的程序在这两棵树上也能正常工作——一棵是最小堆，另一棵是最大堆：

  2     1
 /     /
1     2

另外，要学会正确设置括号；你犯了一个经典错误 True and 42 == 42; 这个表达式的结果是 True。

考虑一下如何处理这两个可能不存在的子节点，尽量用相同的方法。

if left is not None:
  if not <check max heap property for left subtree>: return False
if right is not None:
  if not <check max heap property for right subtree>: return False
return True

缺少的函数应该比较当前节点 并且 在必要时递归进入子树。