判断一棵树是否是BST

很多面试都会问到这样一个问题:
给定一个二叉树，判断它是否是二叉查询树。


思路：
要判断是否是二叉查询树，标准就是看每一个节点是否满足：1、左节点及以下节点的值比它小；2、右节点及以下节点的值比它大。当然，前提是子节点都存在的情况。所以，我们需要从根节点不断向下递归，只要所有节点都满足，那么就是BST，否则，就不是。

代码：

private boolean isBST(Node node) {  
      if (node==null) return(true);  
      if (node.left!=null && maxValue(node.left) > node.data)  return(false);  
      if (node.right!=null && minValue(node.right) <= node.data)  return(false);  
       // check that the subtrees themselves are ok  
      return( isBST(node.left) && isBST(node.right) );  
}  

这个算法的复杂度是 O(n * h)。原因是每做一次递归（向下走），我们都要去查找最大值和最小值。
其实，我们可以不用每次都去查找最大值和最小值，每次向下递归时，我们只要把该节点的值， 作为一个最大值， 传给它的左节点，也就是左边所有节点的值都要比它小；并且把它的值，作为最小值，传给它的右节点，也就是右边所有节点的值都要比它大。每次向下走，分别更新最大值和最小值即可。
代码：

bool isBSTHelper(Node p, int low, int high) {  
  if (p == null) return true;  
  if (low < p.data && p.data < high)  
    return isBSTHelper(p.leftChild, low, p.data) &&  
           isBSTHelper(p.rightChild, p.data, high);  
  else  
    return false;  
}  

bool isBST(Node root) {  
  return isBSTHelper(root, INT_MIN, INT_MAX);  
}  

这样，算法的复杂度就降为 O(n)。