相关疑难解决方法(0)

今天我接受采访时,我被要求编写一个程序,该程序采用二叉树,如果它也是二进制搜索树则返回true,否则为false.

我的方法1:执行有序遍历并将元素存储在O(n)时间内.现在扫描数组/元素列表并检查^第 i ^个索引处的元素是否大于^第(i + 1)^个索引处的元素.如果遇到这种情况,则返回false并退出循环.(这需要O(n)时间).最后回归真实.

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

而且他指着我思考递归.我的方法2:如果对于任何节点N N>左<N和N>右> N,并且N的左节点的有序后继小于N并且有序后继,则BT是BST N的右节点大于N,左右子树是BST.

但这会很复杂,而且运行时间似乎并不好.如果您知道任何最佳解决方案,请帮忙.

我在网上遇到了这个问题，我发现了以下函数来检查 BST 是否有效。但是，我不完全理解最大/最小如何从空更改为可以比较的值。所以在下面的函数中：

//Give the recursive function starting values:

 function checkBST(node) {
  // console.log(node.right);
  return isValidBST(node, null, null);
}


 function isValidBST(node, min, max) {
  console.log(min, max);


  if (node === null) {

    return true;
  }

  if ((max !== null && node.val > max) || (min !== null && node.val < min)) {

    return false;
  }

  if (!isValidBST(node.left, min, node.val) || !isValidBST(node.right, node.val, max)) {

    return false;
  }
  return true;
}



var bst = new BinarySearchTree(8);
bst.insert(3);
bst.insert(1);
bst.insert(6);
bst.insert(10);
bst.insert(4);

当您从左侧的最低深度返回时，它会将最低深度的值与其上方的深度进行比较（即输出 …

给定一个简单的二叉树,我们如何证明树是二叉搜索树？当我们遍历二叉树时,我们如何知道我们所在的节点是否是其父节点的左子节点？我提出了一个解决方案,我将在递归函数调用中传递一些标志,它可以跟踪节点是否是其父节点的左子节点或者我们需要一个父节点指针,我们可以通过它来比较:

if(flag == 'L' && node->value < node->parent->value)
   then continue recursion;
else{
   print "not a binary search tree"
   exit;
}

以同样的方式,需要一个条件R.除此之外你能想到其他任何有效的方法吗？

提前致谢 :)

这种方法是否错误,以确定树是否是BST？节点的左子树仅包含键小于节点键的节点.节点的右子树仅包含键大于节点键的节点.左右子树也必须是二叉搜索树.我的代码是:

isBST(struct node* node) 
{ 
  if (node == NULL) 
    return 1; 
  if (node->left != NULL && node->left->data > node->data) 
    return 0; 
  if (node->right != NULL && node->right->data < node->data) 
    return 0; 
  if (!isBST(node->left) || !isBST(node->right)) 
    return 0; 
  return 1; 
}

验证二叉树是否为BST的最佳算法如下

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
    if(node == null)
        return true;
    if(node.element > MIN 
        && node.element < MAX
        && IsValidBST(node.left,MIN,node.element)
        && IsValidBST(node.right,node.element,MAX))
        return true;
    else 
        return false;
}

这个逻辑的空间复杂性显然O(logN)是我假设的是递归的代价.价值是如何达到的？

我想知道给定的二叉树是否是二叉搜索树.

我不知道该怎么办？

我唯一知道的是BST的inorder遍历将为您提供升序输出.

那么,这是我们需要验证的唯一条件,还是我们要检查的其他内容.

如果还有其他一些必要条件要检查,它们是什么？为什么需要检查这些条件？因为,我认为,如果给定的树是BST,INORDER遍历本身可以很容易地告诉你.

这是我为验证BST而编写的代码.

这是对的吗？如果没有,我该怎么做？

int validate(node *root)
{
    if(root==NULL) return 1;
    else if(root->lchild!=NULL && (root->lchild)->data >=root->data) return 0;
    else if(root->rchild!=NULL && (root->rchild)->data <=root->data) return 0;
    validate(root->lchild);
    validate(root->rchild);
    return 1;
}