您如何验证二叉搜索树？

Question

我在这里阅读了采访中的一项练习，即验证二进制搜索树。这是如何工作的？验证二叉搜索树会寻找什么？我已经写了一个基本的搜索树，但是从未听说过这个概念。

Answer 1

其实那是每个人在面试中犯的错误。

必须根据（minLimitof node，node.value）检查Leftchild

必须根据（node.value，nodeMaxLimit）检查Rightchild

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 

{

     if(node == null)

         return true;

     if(node.element > MIN 

         && node.element < MAX

         && IsValidBST(node.left,MIN,node.element)

         && IsValidBST(node.right,node.element,MAX))

         return true;

     else 

         return false;

}

另一个解决方案（如果空间不是约束）：对树进行有序遍历，并将节点值存储在数组中。如果数组按排序顺序排列，则其有效的BST否则无效。

Answer 2

“验证”二进制搜索树意味着您要检查它的确确实有所有较小的项目在左侧，而较大的项目在右侧。本质上，这是检查二进制树是否为二进制搜索树。

Answer 3

我发现最好的解决方案是O（n），它不占用任何额外空间。它类似于有序遍历，但不是将其存储到数组中然后检查它是否已排序，我们可以采用一个静态变量，并在有序遍历时检查数组是否已排序。

static struct node *prev = NULL;

bool isBST(struct node* root)

{

    // traverse the tree in inorder fashion and keep track of prev node

    if (root)

    {

        if (!isBST(root->left))

          return false;

        // Allows only distinct valued nodes

        if (prev != NULL && root->data <= prev->data)

          return false;

        prev = root;

        return isBST(root->right);

    }

    return true;

}