判断一棵树是否是BST

时间:2022-11-12 10:19:25
很多面试都会问到这样一个问题:
给定一个二叉树,判断它是否是二叉查询树。


思路:
要判断是否是二叉查询树,标准就是看每一个节点是否满足: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)。