您如何验证二叉搜索树？

Question

我在这里阅读了采访中的一项练习，即验证二进制搜索树。

这是如何工作的？验证二叉搜索树会寻找什么？我已经写了一个基本的搜索树，但是从未听说过这个概念。

Answer 1

其实那是每个人在面试中犯的错误。必须根据（minLimitof node，node.value）检查Leftchild必须根据（node.value，nodeMaxLimit）检查RightchildIsValidBST(root,-infinity,infinity);bool IsValidBST(BinaryNode node, int MIN, int MAX)&nbsp;{&nbsp; &nbsp; &nbsp;if(node == null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return true;&nbsp; &nbsp; &nbsp;if(node.element > MIN&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&& node.element < MAX&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&& IsValidBST(node.left,MIN,node.element)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&& IsValidBST(node.right,node.element,MAX))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return true;&nbsp; &nbsp; &nbsp;else&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return false;}另一个解决方案（如果空间不是约束）：对树进行有序遍历，并将节点值存储在数组中。如果数组按排序顺序排列，则其有效的BST否则无效。

Answer 2

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

Answer 3

我发现最好的解决方案是O（n），它不占用任何额外空间。它类似于有序遍历，但不是将其存储到数组中然后检查它是否已排序，我们可以采用一个静态变量，并在有序遍历时检查数组是否已排序。static struct node *prev = NULL;bool isBST(struct node* root){&nbsp; &nbsp; // traverse the tree in inorder fashion and keep track of prev node&nbsp; &nbsp; if (root)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if (!isBST(root->left))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; // Allows only distinct valued nodes&nbsp; &nbsp; &nbsp; &nbsp; if (prev != NULL && root->data <= prev->data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; prev = root;&nbsp; &nbsp; &nbsp; &nbsp; return isBST(root->right);&nbsp; &nbsp; }&nbsp; &nbsp; return true;}