你如何验证二叉搜索树？

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

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

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.

---

"另一个解决方案(如果空间不是约束)执行树的顺序遍历并将节点值存储在数组中.如果数组按排序顺序,则其为有效的BST,否则不会."......嗯,你不要需要_space_或数组才能做到这一点.如果你可以首先进行遍历,并且你要创建的数组应该被排序,那么你在遍历期间访问的每个元素必须比前一个元素更大(或者,在极限情况下,相等),右边？

---

@Yarneo有效的BST不包含重复的节点,所以我相信这个算法是正确的:http://en.wikipedia.org/wiki/Binary_search_tree

---

它不会通过leetcode新的在线测试.将int MIN/MAX更改为BinaryNode null然后分配要比较的节点将有所帮助.

2> wj32..：

---

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

3> Aayush Bahug..：

---

我找到的最佳解决方案是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;
}

4> 小智..：

---

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

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

  std::stack 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;
}

5> Dimagog..：

---

这是我在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)))