查找二叉树是否为二进制搜索树[重复]

7 回答

• 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);      
  }
  

  邀请评论 . 谢谢 .

  回复于 2024-04-30T06:46:06+08:00
• -1

  这是一个非常着名的问题，有以下答案：

  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），因为每个节点都被检查一次 .

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

  回复于 2024-04-30T06:46:06+08:00
• -1

  @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);
  }
  

  回复于 2024-04-30T06:46:06+08:00
• 77

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

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

  回复于 2024-04-30T06:46:06+08:00
• 0

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

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

  回复于 2024-04-30T06:46:06+08:00
• 7

  这是另一个解决方案，它使用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);
      }
  

  回复于 2024-04-30T06:46:06+08:00
• -2

  上面有一些使用INTEGER.MAX AND MIN的例子我无法看到传递它们的理由及其重要性，如果我错了或者解释我原因，请纠正我 .

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

  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 ) )
  
  }
  

  回复于 2024-04-30T06:46:06+08:00