Как вы проверяете бинарное дерево поиска?

Question

Я читал здесь упражнение в интервью, известное как проверка дерева двоичного поиска.

Как именно это работает? Что нужно искать при проверке бинарного дерева поиска? Я написал простое дерево поиска, но никогда не слышал об этом понятии.

Answer 1

На самом деле это ошибка, которую все делают в интервью.

С левой стороны нужно проверить (minLimitof node, node.value)

Rightchild должен быть проверен по (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), и оно не использует лишний пробел. Это похоже на обход по порядку, но вместо того, чтобы сохранять его в массиве, а затем проверять, отсортирован ли он, мы можем взять статическую переменную и проверить при обходе по порядку, отсортирован ли массив.

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

Итеративное решение с использованием обхода по порядку.

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

Answer 6

Вот мой ответ на python, он рассматривает все угловые случаи и хорошо протестирован на сайте хакерранка

""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

def checkBST(root):
    return checkLeftSubTree(root, root.left) and checkRightSubTree(root, root.right)

def checkLeftSubTree(root, subTree):
    if not subTree:
        return True
    else:
        return root.data > subTree.data \
        and checkLeftSubTree(root, subTree.left) \ 
        and checkLeftSubTree(root, subTree.right) \
        and checkLeftSubTree(subTree, subTree.left) \
        and checkRightSubTree(subTree, subTree.right)

def checkRightSubTree(root, subTree):
    if not subTree:
        return True
    else:
        return root.data < subTree.data \ 
        and checkRightSubTree(root, subTree.left) \
        and checkRightSubTree(root, subTree.right) \
        and checkRightSubTree(subTree, subTree.right) \
        and checkLeftSubTree(subTree, subTree.left)

Answer 7

Поскольку обратный порядок следования BST является неубывающей последовательностью, мы могли бы использовать это свойство, чтобы судить, является ли двоичное дерево BST или нет. Используя обход Морриса и поддерживая узел pre, мы можем получить решение за O (n) времени и O (1) пространства сложности. Вот мой код

public boolean isValidBST(TreeNode root) {
    TreeNode pre = null, cur = root, tmp;
    while(cur != null) {
        if(cur.left == null) {
            if(pre != null && pre.val >= cur.val) 
                return false;
            pre = cur;
            cur = cur.right;
        }
        else {
            tmp = cur.left;
            while(tmp.right != null && tmp.right != cur)
                tmp = tmp.right;
            if(tmp.right == null) { // left child has not been visited
                tmp.right = cur;
                cur = cur.left;
            }
            else { // left child has been visited already
                tmp.right = null;
                if(pre != null && pre.val >= cur.val) 
                    return false;
                pre = cur;
                cur = cur.right;
            }
        }
    }
    return true;
}

Answer 8

"Лучше сначала определить инвариант. Здесь инвариант - любые два последовательных элемента BST при прохождении по порядку должны быть в строго возрастающем порядке их появления (не может быть равным, всегда увеличиваться в обход по порядку). Таким образом, решение может быть простым обходом по порядку с запоминанием последнего посещенного узла и сравнением текущего узла с последним посещенным узлом с '<' (или '>'). "

Answer 9

В Java и разрешение узлов с одинаковым значением в любом поддереве:

public boolean isValid(Node node) {
    return isValid(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isValid(Node node, int minLimit, int maxLimit) {
    if (node == null)
        return true;
    return minLimit <= node.value && node.value <= maxLimit
            && isValid(node.left, minLimit, node.value)
            && isValid(node.right, node.value, maxLimit);
}

Answer 10

Недавно я получил этот вопрос в телефонном интервью и боролся с ним больше, чем следовало бы. Я пытался отслеживать минимумы и максимумы в дочерних узлах, и я просто не мог обернуть свой мозг вокруг различных случаев под давлением интервью.

Подумав об этом, засыпая прошлой ночью, я понял, что это так же просто, как отслеживать последний узел, который вы посетили во время обхода inorder. В Java:

public <T extends Comparable<T>> boolean isBst(TreeNode<T> root) {
    return isBst(root, null);
}

private <T extends Comparable<T>> boolean isBst(TreeNode<T> node, TreeNode<T> prev) {
    if (node == null)
        return true;

    if (isBst(node.left, prev) && (prev == null || prev.compareTo(node) < 0 ))
        return isBst(node.right, node);

    return false;
}