算法11—判断一个树是不是二叉查询树

本文主要是介绍算法11—判断一个树是不是二叉查询树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题：

给定一个二叉树，判断它是否是二叉查询树。

思路：

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

代码：

[java]  view plain copy  
 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)。原因是每做一次递归（向下走），我们都要去查找最大值和最小值。

其实，我们可以不用每次都去查找最大值和最小值，每次向下递归时，我们只要把该节点的值，作为一个最大值，传给它的左节点，也就是左边所有节点的值都要比它小；并且把它的值，作为最小值，传给它的右节点，也就是右边所有节点的值都要比它大。每次向下走，分别更新最大值和最小值即可。

代码：

[java]  view plain copy  
 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);  
 }  