int isBST(struct node* node)
{
if (node==NULL) return(true);
//如果左子树最大值>=当前node的值，则返回false
if (node->left!=NULL && maxValue(node->left) >= node->data)
return(false);
// 如果右子树最小值<=当前node的值，返回false
if (node->right!=NULL && minValue(node->right) <= node->data)
return(false);
// 如果左子树或者右子树不是BST，返回false
if (!isBST(node->left) || !isBST(node->right))
return(false);
// 通过所有测试，返回true
return(true);
}
解法2：更好的解法
以前面提到的binary tree(1)为例，当我们从结点10遍历到右结点15时，我们知道右子树结点值肯定都在10和+INFINITY（无穷大）之间。当我们遍历到结点15的左孩子结点6时，我们知道结点15的左子树结点值都必须在10到15之间。显然，结点6不符合条件，因此它不是一棵二叉搜索树。该算法代码如下：
int isBST2(struct node* node)
{
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
给定的二叉树是BST则返回true，且它的值 >min 以及 < max.
*/
int isBSTUtil(struct node* node, int min, int max)
{
if (node==NULL) return(true);
// 如果不满足min和max约束，返回false
if (node->data<=min || node->data>=max) return(false);
// 递归判断左右子树是否满足min和max约束条件
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data, max)
);
}
由于该算法只需要访问每个结点1次，因此时间复杂度为O(n)，比解法1效率高很多。
解法3：中序遍历算法
因为一棵二叉搜索树的中序遍历后其结点值是从小到大排好序的，所以依此给出下面的解法。该解法时间复杂度也是O(n)。
bool isBSTInOrder(BinaryTree *root)
{
int prev = INT_MIN;
return isBSTInOrderHelper(root, prev);
}
/*该函数判断二叉树p是否是一棵二叉搜索树，且其结点值都大于prev*/
bool isBSTInOrderHelper(BinaryTree *p, int& prev)
{
if (!p) return true;
if (isBSTInOrderHelper(p->left, prev)) { // 如果左子树是二叉搜索树，且结点值都大于prev
if (p->data > prev) { //判断当前结点值是否大于prev，因为此时prev已经设置为已经中序遍历过的结点的最大值。
prev = p->data;
return isBSTInOrderHelper(p->right, prev); //若结点值大于prev，则设置prev为当前结点值，并判断右子树是否二叉搜索树且结点值都大于prev。
} else {
return false;
}
}
else {
return false;
}
}
