};方法1 (实现简单，但却是错误的)对于每个节点，检测它的左孩子节点是否小于它，且右孩子节点是否大于它。bool isBST(Node* node){ if (node == NULL)return true;//如果左孩子大于根节点，则不是BST if (node->left != NULL && node->left->key> node->key)return false;//如果右孩子节点小于根节点，则不是BST if (node->right != NULL && node->right->key < node->key)return false;//递归的判断 if (!isBST(node->left) || !isBST(node->right))return false;//检测完毕，所有条件通过，则是BST return true;}但是，这种判断方法是错误的，如下面例子所示，节点4处于根节点3的左子树中，但是函数检测到这棵树是BST. 3 / \ 2 5 / \1 4方法2 (结果正确，但是效率比较低)对于每个节点，检测左子树中的最大值是否比它小，而右子树的最小值比它大。//如果是BST，则返回truebool isBST(Node * node ){if ( node == NULL)return true;//如果左子树最大值大于根节点，则返回falseif ( node->left != NULL && maxValue( node->left) > node->key)return false;//如果右子树最小值小于根节点，则返回falseif ( node->right != NULL && minValue( node->right) < node->key)return false;//递归判断if (!isBST( node->left) || !isBST( node->right))return( false);//所有检测都通过，是BSTreturn true;}其中，maxValue以及minValue函数，分别返回一颗非空树中的最大值和最小值。方法3 (正确并且有效的)方法2因为要重复的遍历树中的部分数据，效率比较低。更好的方案是每个节点只遍历一次。 方法3的巧妙之处在于限定了子树中节点值的范围，从而每个节点只需访问一次。节点值的初始范围可限定为INT_MIN以及INT_MAX。//判断是否为BSTbool isBST(Node* node) { return(isBSTUtil(node, INT_MIN, INT_MAX)); } //如果是一颗二叉查找树，且值范围在[min,max]，则返回truebool isBSTUtil(Node* node, int min, int max) 代码实现:#include <iostream>struct Node{int key;Node *left;Node *right;};bool isBSTUtil(Node * node, int min, int max);//判断是否为BSTbool isBST(Node * node ){return(isBSTUtil( node, INT_MIN, INT_MAX));}//如果是一颗二叉查找树，且值范围在[min, max]，则返回truebool isBSTUtil(Node * node , int min , int max ){//空树也是BSTif ( node == NULL)return true;//如果节点值违反了最大/最小约束条件，则不是BSTif ( node->key < min || node->key > max)return false;//递归检查子树return isBSTUtil( node->left, min, node->key – 1) &&isBSTUtil( node->right, node->key + 1, max);}// 创建一个新的BST节点Node *createNewNode(int item ){Node *temp = new Node;temp->key = item;temp->left = temp->right = NULL;return temp;}int main(){/* tree1的定义4/ \25/ \1 3*/Node *root = createNewNode(4);root->left = createNewNode(2);root->right = createNewNode(5);root->left->left = createNewNode(1);root->left->right = createNewNode(3);if (isBST(root))std::cout << "tree1 is BST\n";elsestd::cout << "tree1 is not BST\n";/* tree2的定义4/ \25//13*/root = createNewNode(4);root->left = createNewNode(2);root->left->left = createNewNode(1);root->right = createNewNode(5);root->right->left = createNewNode(3);if (isBST(root))std::cout << "tree2 is BST\n";elsestd::cout << "tree2 is not BST\n";return 0;}输出：tree1 is BSTtree2 is not BST时间复杂度: O(n)辅助空间 : 如果不考虑函数调用栈的大小，则为O(1)， 否则为O(n)方法4(使用中序遍历)1) 对树进行中序遍历，将结果保存在temp数组中。3) 检测temp数组中元素是否为升序排列。如果是，则这棵树为BST.时间复杂度: O(n)方法4还可以进一步的优化，我们可以避免使用这个额外的数组。在中序遍历时，可以保存前驱节点，如果当前节点小于前驱节点，则这棵树不是BST.//判断是否为BSTbool isBST(Node* root){static Node *prev = NULL;// 中序遍历这棵树，，并保存前驱节点至prev中if (root){if (!isBST(root->left))return false;// 检测节点值的合法性if (prev != NULL && root->key <= prev->key)return false;prev = root;//右子树return isBST(root->right);}return true;}更多参考:
你可能付出一定的代价，但日后你得到的，远比付出的多得多。
