你如何验证二叉搜索树？

Question

我在这里读到了一个名为验证二叉搜索树的访谈练习.

这究竟是如何工作的？在验证二叉搜索树时会有什么需要？我写了一个基本的搜索树,但从未听说过这个概念.

Answer 1

实际上,这是每个人在面试中所犯的错误.

必须检查Leftchild(minLimitof node,node.value)

必须检查右子节点(node.value,节点的MaxLimit)

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

另一种解决方案(如果空间不是约束):执行树的顺序遍历并将节点值存储在数组中.如果数组按排序顺序排列,则不是有效的BST.

Answer 2

"验证"二进制搜索树意味着您检查它确实包含左侧的所有较小项目和右侧的大项目.本质上,它是检查二叉树是否是二叉搜索树的检查.

Answer 3

我找到的最佳解决方案是O(n),它不使用额外的空间.它类似于inorder遍历,但不是将其存储到数组中,然后检查它是否已排序,我们可以采用静态变量并检查,同时遍历是否对数组进行排序.

static struct node *prev = NULL;

bool isBST(struct node* root)
{
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;

        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
          return false;

        prev = root;

        return isBST(root->right);
    }

    return true;
}

Answer 4

使用inorder遍历的迭代解决方案.

bool is_bst(Node *root) {
  if (!root)
    return true;

  std::stack<Node*> stack;
  bool started = false;
  Node *node = root;
  int prev_val;

  while(true) {
    if (node) {
      stack.push(node);
      node = node->left();
      continue;
    }
    if (stack.empty())
      break;
    node = stack.top();
    stack.pop();

    /* beginning of bst check */
    if(!started) {
      prev_val = node->val();
      started = true;
    } else {
      if (prev_val > node->val())
        return false;
      prev_val = node->val();
    }
    /* end of bst check */

    node = node->right();
  }
  return true;
}

Answer 5

这是我在Clojure中的解决方案:

(defstruct BST :val :left :right)

(defn in-order [bst]
  (when-let [{:keys [val, left, right]} bst]
    (lazy-seq
      (concat (in-order left) (list val) (in-order right)))))

(defn is-strictly-sorted? [col]
  (every?
    (fn [[a b]] (< a  b))
    (partition 2 1 col)))

(defn is-valid-BST [bst]
  (is-strictly-sorted? (in-order bst)))