使用 Level Order Traversal 检查 BST

Question

所以我一直在尝试来自 Hackerrank 的问题，并且有一个关于检查树是否是 BST 的问题。我一直在使用级别顺序遍历进行此检查。如果 node.left.value> node.value 且 node.right.value

除了我没有检查单个根节点的情况外，其他所有测试用例都失败了。我哪里出错了？

def checkBST(root):
    
    # if root.left and root.right is None:
    #     return True
    if not root:
            return
    flag=0
    q=[root]
    while len(q)>0:
        temp=q.pop(0)
        if temp.left is not None:
            if temp.left.data> temp.data:
                flag=1
                break
            else:
                q.append(temp.left)
        if temp.right is not None:
            if temp.right.data<temp.data:
                flag=1
                break
            else:
                q.append(temp.right)
            
    if flag==1:
        return False
    else:
        return True

Answer 1

仅仅测试直接子项与其父项的关系是否正确是不够的。所有这些 comparison-tests 都通过了无效的 BST。您需要确保在节点的 whole 左子树中没有节点的值大于该节点的值。

所以层序遍历并不是执行此操作的正确工具。使用 in-order 遍历会更好，因为 BST 将具有 non-decreasing in-order 遍历。

使用 Level Order Traversal 检查 BST

Check for BST using Level Order Traversal

python

binary-search-tree