答案转载自：https://www.2cto.com/kf/201506/408372.html

裁判测试程序样例：

#include 
     
      #include 
      
       typedef enum { false, true } bool;typedef int ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode{    ElementType Data;    BinTree Left;    BinTree Right;};BinTree BuildTree(); /* 由裁判实现，细节不表 */bool IsBST ( BinTree T );int main(){    BinTree T;    T = BuildTree();    if ( IsBST(T) ) printf("Yes\n");    else printf("No\n");    return 0;}/* 你的代码将被嵌在这里 */
      
     

 

 错误解法：

1 bool isBST(Node* node) 2 { 3   if (node == NULL) 4     return true; 5        6   //如果左孩子大于根节点，则不是BST 7   if (node->left != NULL && node->left->key> node->key) 8     return false; 9       10   //如果右孩子节点小于根节点，则不是BST11   if (node->right != NULL && node->right->key < node->key)12     return false;13     14   //递归的判断15   if (!isBST(node->left) || !isBST(node->right))16     return false;17       18   //检测完毕，所有条件通过，则是BST19   return true;20 }

这种判断方法是错误的，如下面例子所示，节点4处于根节点3的左子树中，但是函数检测到这棵树是BST.

 

正确解法：

1 //判断是否为BST 2 bool IsBST(BinTree T) 3 { 4         return(isBSTUtil( T, -10000, 10000)); 5 } 6  7 //如果是一颗二叉查找树，且值范围在[min, max]，则返回true 8 bool isBSTUtil(BinTree T , int min , int max ) 9 {10         //空树也是BST11         if ( T == NULL)12                return true;13 14         //如果节点值违反了最大/最小约束条件，则不是BST15         if ( T->Data < min || T->Data > max)16                return false;17 18         //递归检查子树19         return  isBSTUtil( T->Left, min, T->Data - 1) &&20               isBSTUtil( T->Right, T->Data + 1, max);21 }