O（log n）中的二进制搜索树？

Question

给定一个有 n 个节点的二叉树，是否可以在 O(log n) 时间复杂度内检查给定树是否为 BST？

Answer 1

如果 n 是节点的数量，那么不会，因为您至少需要查看所有值一次，所以您至少需要 O(n)。但是如果你将 n 定义为一些特殊的东西，比如子树的总数，你就可以实现这个。 （然而，这样做有点愚蠢，因为这有点像说如果你有 100 美分而不是 1 欧元，你就会有更多的钱。它可能看起来更令人印象深刻但也很奇怪并且没有附加值，这只是令人困惑一起工作，而普通人不会这样做）

这是 O(n) 算法：如果它是 BST，那么左树和右树都是 BST，其中所有值都在某个最小值和最大值之间，因此您可以创建一个递归方法有点像这样：

public boolean isBST(subtree, minvalue, maxvalue){
    root=root of subtree;
    if(root>maxvalue || root<minvalue) return false;
    if(has left child)
        if(!isBST(left-child-tree, minvalue, rootvalue)) return false;
    if(has right child)
        if(!isBST(right-child-tree, rootvalue, maxvalue)) return false;
    return true;
}

你用 isBST(tree, -infinity, +infinity) 调用这个方法。这是伪代码，当然可以更好地实现。