33

今天我有一个面试，我被要求编写一个程序，它接受一个二叉树，如果它也是一个二叉搜索树则返回 true，否则返回 false。

我的方法1：执行有序遍历并将元素存储在 O(n) 时间内。现在扫描元素的数组/列表并检查第 i个索引处的元素是否大于第 (i+1)个索引处的元素。如果遇到这样的条件，则返回 false 并跳出循环。（这需要 O(n) 时间）。最后返回真。

但是这位先生希望我提供一个有效的解决方案。我尝试过，但没有成功，因为要确定它是否是 BST，我必须检查每个节点。

此外，他指出我要考虑递归。我的方法2：如果对于任何节点 N N->left 是 < N 和 N->right > N ，并且 N 的左节点的有序后继小于 N 并且有序后继，则 BT 是 BST N的右节点大于N，左右子树是BST。

但这将是复杂的，运行时间似乎并不好。如果您知道任何最佳解决方案，请提供帮助。

4

7 回答 7

78

以下答案是一个众所周知的问题：

public boolean isValid(Node root) {
     return isValidBST(root, Integer.MIN_VALUE,
          Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int l, int h) {
     if(node == null)
         return true;
     return node.value > l 
         && node.value < h
         && isValidBST(node.left, l, node.value)
         && isValidBST(node.right, node.value, h);
}

递归调用确保子树节点在其祖先的范围内，这很重要。运行时间复杂度为 O(n)，因为每个节点都被检查一次。

另一种解决方案是进行中序遍历并检查序列是否已排序，特别是因为您已经知道提供了二叉树作为输入。

于 2012-05-31T11:37:13.363 回答
7

@Dhruv 提供的答案很好。除此之外，这是另一种在 O(n) 时间内工作的解决方案。
在这种方法中，我们需要跟踪前一个节点。在每次递归调用中，我们都会检查前一个节点数据和当前节点数据。如果当前节点数据小于前一个，我们返回 false

int isBST(node* root) {
  static node* prev  = NULL;

  if(root==NULL)
    return 1;

  if(!isBST(root->left))
    return 0;

  if(prev!=NULL && root->data<=prev->data)
    return 0;

  prev = root;
  return isBST(root->right);
}

于 2014-03-19T05:56:42.190 回答
1 
boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max){
  if(node == null){
    return true;
  }

  boolean left  = isBinarySearchTree(node.getLeft(), min, node.getValue());
  boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

  return left && right && (node.getValue()<max) && (node.getValue()>=min);      
}

欢迎评论。谢谢。

于 2013-02-28T06:22:51.017 回答
0

我认为第二种方法是对的。可以递归方式遍历树。在每次迭代中，可以存储当前子树的下界和上界。如果我们要检查具有根 x 的子树，并且子树的边界是 l 和 h，那么我们只需要检查 l <= x <= h 并检查具有边界 l 和 x 的左子树，以及右一个边界为 x 和 h。

这将具有 O(n) 复杂度，因为我们从根开始，并且每个节点仅作为某个子树的根检查一次。此外，递归调用需要 O(h) 内存，其中 h 是树的高度。

于 2012-05-31T11:24:44.177 回答
-1

上面有一些使用 INTEGER.MAX AND MIN 的示例我看不出通过它们的理由及其意义，如果我错了，请纠正我或解释原因。

更多的二叉搜索树可能有通过 compareTo 方法或 Cooper 比较的对象..（因此 Integer.MIN 和 Integer.MAX 不适合该模型）我正在编写一个返回 true 或 false 的代码，必须调用（root_node ,true) 如果是 bst 则返回 true 否则返回 false

void boolean isBSt( node root_node, boolean passed_root)
{

  if ( node==null){
        if ( passed_root)
        return false;
        // you have passed null pointer as 
        //root of the tree , since there is no 
        // valid start point we can throw an exception or return false      
        return true;
   }

  if( node.right !=null ) 
     if ( node.right.data <= node.data)
   return false;

  if ( node.left !=null ) 
        if ! ( node.left.data <= node.data) 
    return false;

  return ( isBST( node.right , false) && isBST( node.left, false ) )

}
于 2013-05-21T08:55:54.107 回答
-1

看看这个解决方案：http: //preparefortechinterview.blogspot.com/2013/09/am-i-bst.html

它解释了不同的方法，并为您提供了一种通用且有效的方法。希望能帮助到你。

于 2013-09-27T00:01:44.987 回答
-2

这是另一个解决方案，它使用 2 个辅助函数来使用辅助函数 minValue 和 maxValue 为每个节点计算子树中的最小值和最大值

int isBST(struct node* node)
    {
      if (node == NULL)
        return(true); 

      /* false if the max of the left is > than us */
        if (node->left!=NULL && maxValue(node->left) > node->data)
            return(false); 

      /* false if the min of the right is <= than us */
        if (node->right!=NULL && minValue(node->right) < node->data)
            return(false); 

      /* false if, recursively, the left or right is not a BST */ 
         if (!isBST(node->left) || !isBST(node->right))
           return(false); 

      /* passing all that, it's a BST */
          return(true);
    }
于 2012-06-10T04:32:42.187 回答