由一道小库科技笔试题而生出来的一篇博文，题目如下：

给予一个二叉树的根节点，验证该树是否是二叉搜索树，在O(n)时间内，用熟悉的语言写出算法。

不了解二叉搜索树的盆友可以先移步《数据结构二叉树之闲死攻略（二）》

二叉搜索树两个基本的性质

1. 顺序性（左<根<右）

2. 单调性（小到大）

1. 二叉树结点定义

C++

struct TreeNode{ int data; TreeNode *left; TreeNode *right; };

Java

class BinaryNode{ Object element; BinaryNode left; BinaryNode right; }

方法1 (错误)

对每一个节点，检测其值是否大于左子树节点，是否小于右子树节点。思路简单。

C++

bool isBST(TreeNode* root) { if (root == NULL) return true; if (root->left != NULL && root->left->data> root->data) return false; if (root->right != NULL && root->right->data < root->data) return false; if (!isBST(root->left) || !isBST(root->right)) return false; return true; }

Java

但是，这种方法是错误的，如下面例子，节点4大于根节点3，但上面函数检测这棵树是BST。

               3

            /      \

          2         5

       /     \

    1         4

方法2 

对每个节点，检测其值是否大于左子树的最大值，是否小于右子树的最小值。思路正确，但效率较低。

C++

int maxValue(TreeNode *root) { int max = root->data; if(root->left != NULL) { int maxLeft = maxValue(root->left); max = max > maxLeft ? max : maxLeft; } if(root->right != NULL) { int maxRight = maxValue(root->right); max = max > maxRight ? max : maxRight; } return max; } int minValue(TreeNode *root) { int min = root->data; if(root->left != NULL) { int minLeft = maxValue(root->left); min = min > minLeft ? min : minLeft; } if(root->right != NULL) { int minRight = maxValue(root->right); min = min > minRight ? min : min; } return min; } bool isBST(TreeNode *root) { if(root == NULL) return true; if(root->left != NULL && maxValue(root->left) > root->data) return false; if(root->right != NULL && minValue(root->right) < root->data) return false; return isBST(root->left) && isBST(root->right); }

其中，maxValue及minValue函数，分别返回一棵非空二叉树的最大值和最小值。

Java

 

方法3

方法2需要重复遍历树中的部分数据，故效率较低，如果只需每个节点遍历一次，那么效率将大大提高。方法3的巧妙之处在于限定了子树节点的值得范围，从而每个节点只需遍历一次。节点值的初始范围可限定为TNT_MIN以及TNT_MAX。

C++

bool isBSTUtil(TreeNode *root, int min, int max) { if(root == NULL) return true; if(root->data < min || root->data > max) return false; return isBSTUtil(root->left, min, root->data - 1) && isBSTUtil(root->right, root->data + 1, max); } bool isBST(TreeNode *root) { return isBST02(root, INT_MIN, INT_MAX); }

Java

方法4

使用中序遍历的方法实现：

1）对树进行中序遍历，将结果保存在temp数组中；

2）检测temp数组是否为升序排列，如果是，则为BST，反之则不是。

此方法还可以进一步的优化，不用temp数组，避免使用额外的内存开销。在中序遍历时使用静态变量保存前驱节点，如果当前节点小于前驱节点，则该树不是BST。

C++

//中序遍历的方法实现 bool isBST(TreeNode *root) { static TreeNode *prev; if(root != NULL) { if(!isBST(root->left)) return false; if(prev != NULL && root->data < prev->data) return false; prev = root; if(!isBST(root->right)) return false; } return true; }

Java

 

 

 

 

 

 

 

 

 

 

 

 

---

参考自：《判断一棵树是否是二叉搜索树》