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

Question

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

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

Answer 1

«Проверка» двоичного дерева поиска означает, что вы проверяете, что у него действительно есть все мелкие предметы слева и большие предметы справа. По существу, это проверка, чтобы узнать, является ли двоичное дерево двоичным. поиск дерево.

Answer 2

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

LeftChild должен быть проверен против (minLimitof узла, 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; 
} 

Другим решения (если пространство не является constraint): Проведите обход дерева по порядку и сохраните значения узлов в массиве. Если массив находится в отсортированном порядке, то его действительный BST в противном случае нет.

Answer 3

Вот мое решение в 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 4

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

Answer 5

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

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 6

Рекурсивный решение:

isBinary(root) 
    { 
     if root == null 
      return true 
     else if(root.left == NULL and root.right == NULL) 
      return true 
     else if(root.left == NULL) 
      if(root.right.element > root.element) 
       rerturn isBInary(root.right) 
     else if (root.left.element < root.element) 
       return isBinary(root.left) 
     else 
       return isBInary(root.left) and isBinary(root.right) 

    } 

Answer 7

bool BinarySearchTree::validate() { 
    int minVal = -1; 
    int maxVal = -1; 
    return ValidateImpl(root, minVal, maxVal); 
} 

bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal) 
{ 
    int leftMin = -1; 
    int leftMax = -1; 
    int rightMin = -1; 
    int rightMax = -1; 

    if (currRoot == NULL) return true; 

    if (currRoot->left) { 
     if (currRoot->left->value < currRoot->value) { 
      if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false; 
      if (leftMax != currRoot->left->value && currRoot->value < leftMax) return false; 
     } 
     else 
      return false; 
    } else { 
     leftMin = leftMax = currRoot->value; 
    } 

    if (currRoot->right) { 
     if (currRoot->right->value > currRoot->value) { 
      if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false; 
      if (rightMin != currRoot->right->value && currRoot->value > rightMin) return false; 
     } 
     else return false; 
    } else { 
     rightMin = rightMax = currRoot->value; 
    } 

    minVal = leftMin < rightMin ? leftMin : rightMin; 
    maxVal = leftMax > rightMax ? leftMax : rightMax; 

    return true; 
} 

Answer 8

// using inorder traverse based Impl 
bool BinarySearchTree::validate() { 
    int val = -1; 
    return ValidateImpl(root, val); 
} 

// inorder traverse based Impl 
bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) { 
    if (currRoot == NULL) return true; 

    if (currRoot->left) { 
     if (currRoot->left->value > currRoot->value) return false; 
     if(!ValidateImpl(currRoot->left, val)) return false; 
    } 

    if (val > currRoot->value) return false; 
    val = currRoot->value; 

    if (currRoot->right) { 
     if (currRoot->right->value < currRoot->value) return false; 
     if(!ValidateImpl(currRoot->right, val)) return false; 
    } 
    return true; 
} 

Answer 9

boolean isBST(Node root) { 
    if (root == null) { return true; } 
    return (isBST(root.left) && (isBST(root.right) && (root.left == null || root.left.data <= root.data) && (root.right == null || root.right.data > root.data)); 
} 

Answer 10

Вот итерационный решение без использования дополнительного пространства.

Node{ 
    int value; 
    Node right, left 
    } 

    public boolean ValidateBST(Node root){ 
    Node currNode = root; 
    Node prevNode = null; 
    Stack<Node> stack = new Stack<Node>(); 
    while(true){ 
     if(currNode != null){ 
      stack.push(currNode); 
      currNode = currNode.left; 
      continue; 
     } 
     if(stack.empty()){ 
      return; 
     } 
     currNode = stack.pop(); 
     if(prevNode != null){ 
      if(currNode.value < prevNode.value){ 
       return false; 
      } 
     } 
     prevNode = currNode; 
     currNode = currNode.right; 
    } 
} 

Answer 11

bool ValidateBST(Node *pCurrentNode, int nMin = INT_MIN, int nMax = INT_MAX) 
{ 
    return 
    (
     pCurrentNode == NULL 
    ) 
    || 
    (
     (
      !pCurrentNode->pLeftNode || 
      (
       pCurrentNode->pLeftNode->value < pCurrentNode->value && 
       pCurrentNode->pLeftNode->value < nMax && 
       ValidateBST(pCurrentNode->pLeftNode, nMin, pCurrentNode->value) 
      ) 
     ) 
     && 
     (
      !pCurrentNode->pRightNode || 
      (
       pCurrentNode->pRightNode->value > pCurrentNode->value && 
       pCurrentNode->pRightNode->value > nMin && 
       ValidateBST(pCurrentNode->pRightNode, pCurrentNode->value, nMax) 
      ) 
     ) 
    ); 
} 

Answer 12

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

Чтобы узнать, является ли данный BT BST для любого типа данных, вам нужно пойти с подходом ниже. 1. вызвать рекурсивную функцию до конца листового узла с использованием обходного порядка 2. Создайте свои минимальные и максимальные значения самостоятельно.

Элемент дерева должен иметь меньше или больше заданного оператора.

#define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal) 
#define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal) 

template <class T> 
bool IsValidBST (treeNode &root) 
{ 

    T min, max; 
    return IsValidBST (root, &min, &max); 
} 

template <class T> 
bool IsValidBST (treeNode *root, T *MIN , T *MAX) 
{ 
    T leftMin, leftMax, rightMin, rightMax; 
    bool isValidBST; 

    if (root->leftNode == NULL && root->rightNode == NULL) 
    { 
     *MIN = root->element; 
     *MAX = root->element; 
     return true; 
    } 

    isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax); 

    if (isValidBST) 
    isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax); 

    if (isValidBST) 
    { 
    *MIN = MIN (leftMIN, rightMIN); 
    *Max = MAX (rightMax, leftMax); 
    } 

    return isValidBST; 
} 

Answer 14

bool isBST(struct node* root) 
{ 
    static struct node *prev = NULL; 
    // 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 15

рекурсии легко, но итерационный подход лучше, есть один итерационный вариант выше, но это слишком сложно, чем это необходимо. Вот решение лучше в c++ вы когда-нибудь где-нибудь:

Этот алгоритм работает в O(N) времени и нуждается в O(lgN) пространство.

struct TreeNode 
{ 
    int value; 
    TreeNode* left; 
    TreeNode* right; 
}; 

bool isBST(TreeNode* root) { 
    vector<TreeNode*> stack; 
    TreeNode* prev = nullptr; 
    while (root || stack.size()) { 
     if (root) { 
      stack.push_back(root); 
      root = root->left; 
     } else { 
      if (prev && stack.back()->value <= prev->value) 
       return false; 
      prev = stack.back(); 
      root = prev->right;      
      stack.pop_back(); 
     } 
    } 
    return true; 
} 

Answer 16

Я написал решение использовать Симметричный Traversal BST и проверить, является ли узлы в порядке возрастания для пространства O(1) и времени O(n). TreeNode predecessor - это предыдущий узел. Я не уверен, что это правильно или нет. Поскольку обход границы не может определить целое дерево.

public boolean isValidBST(TreeNode root, TreeNode predecessor) { 
    boolean left = true, right = true; 
    if (root.left != null) { 
     left = isValidBST(root.left, predecessor); 
    } 
    if (!left) 
     return false; 

    if (predecessor.val > root.val) 
     return false; 

    predecessor.val = root.val; 
    if (root.right != null) { 
     right = isValidBST(root.right, predecessor); 
    } 

    if (!right) 
     return false; 

    return true; 

} 

Answer 17

Ниже реализация Java из BST проверки, где мы путешествуем дерево в заказе DFS и возвращает ложь, если мы получим любое число, которое больше, чем последний номер.

static class BSTValidator { 
    private boolean lastNumberInitialized = false; 
    private int lastNumber = -1; 

    boolean isValidBST(TreeNode node) { 
    if (node.left != null && !isValidBST(node.left)) return false; 

    // In-order visiting should never see number less than previous 
    // in valid BST. 
    if (lastNumberInitialized && (lastNumber > node.getData())) return false; 
    if (!lastNumberInitialized) lastNumberInitialized = true; 

    lastNumber = node.getData(); 

    if (node.right != null && !isValidBST(node.right)) return false; 

    return true; 
    } 
} 

Answer 18

Поскольку в заказе обход из BST не является снижение последовательности, мы можем использовать это свойство, чтобы судить о том, бинарное дерево BST или нет. Используя Morris traversal и поддерживая узел 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 19

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

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

Answer 20

Итерационное решение.

private static boolean checkBst(bst node) { 

    Stack<bst> s = new Stack<bst>(); 
    bst temp; 
    while(node!=null){ 
     s.push(node); 
     node=node.left; 
    } 
    while (!s.isEmpty()){ 
     node = s.pop(); 
     System.out.println(node.val); 
     temp = node; 
     if(node.right!=null){ 
      node = node.right; 
      while(node!=null) 
      { 
       //Checking if the current value is lesser than the previous value and ancestor. 
       if(node.val < temp.val) 
        return false; 
       if(!s.isEmpty()) 
        if(node.val>s.peek().val) 
         return false; 
       s.push(node); 
       if(node!=null) 
       node=node.left; 
      } 
     } 
    } 
    return true; 
} 

Answer 21

Это работает для дубликатов.

// time O(n), space O(logn) 
// pseudocode 
is-bst(node, min = int.min, max = int.max): 
    if node == null: 
     return true 
    if node.value <= min || max < node.value: 
     return false 
    return is-bst(node.left, min, node.value) 
     && is-bst(node.right, node.value, max) 

Это работает даже для int.min и int.max значений с помощью Nullable типов.

// time O(n), space O(logn) 
// pseudocode 
is-bst(node, min = null, max = null): 
    if node == null: 
     return true 
    if min != null && node.value <= min 
     return false 
    if max != null && max < node.value: 
     return false 
    return is-bst(node.left, min, node.value) 
     && is-bst(node.right, node.value, max) 

Answer 22

Вдохновленный http://www.jiuzhang.com/solutions/validate-binary-search-tree/

Есть два основных решения: обход и разделить & & властвуй.

public class validateBinarySearchTree { 
    public boolean isValidBST(TreeNode root) { 
     return isBSTTraversal(root) && isBSTDivideAndConquer(root); 
    } 

    // Solution 1: Traversal 
    // The inorder sequence of a BST is a sorted ascending list 
    private int lastValue = 0; // the init value of it doesn't matter. 
    private boolean firstNode = true; 
    public boolean isBSTTraversal(TreeNode root) { 
     if (root == null) { 
      return true; 
     } 

     if (!isValidBST(root.left)) { 
      return false; 
     } 

     // firstNode is needed because of if firstNode is Integer.MIN_VALUE, 
     // even if we set lastValue to Integer.MIN_VALUE, it will still return false 
     if (!firstNode && lastValue >= root.val) { 
      return false; 
     } 

     firstNode = false; 
     lastValue = root.val; 

     if (!isValidBST(root.right)) { 
      return false; 
     } 

     return true; 

    } 

    // Solution 2: divide && conquer 
    private class Result { 
     int min; 
     int max; 
     boolean isBST; 
     Result(int min, int max, boolean isBST) { 
      this.min = min; 
      this.max = max; 
      this.isBST = isBST; 
     } 
    } 

    public boolean isBSTDivideAndConquer(TreeNode root) { 
     return isBSTHelper(root).isBST; 
    } 

    public Result isBSTHelper(TreeNode root) { 
     // For leaf node's left or right 
     if (root == null) { 
      // we set min to Integer.MAX_VALUE and max to Integer.MIN_VALUE 
      // because of in the previous level which is the leaf level, 
      // we want to set the min or max to that leaf node's val (in the last return line) 
      return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, true); 
     } 

     Result left = isBSTHelper(root.left); 
     Result right = isBSTHelper(root.right); 

     if (!left.isBST || !right.isBST) { 
      return new Result(0,0, false); 
     } 

     // For non-leaf node 
     if (root.left != null && left.max >= root.val 
       && root.right != null && right.min <= root.val) { 
      return new Result(0, 0, false); 
     } 

     return new Result(Math.min(left.min, root.val), 
       Math.max(right.max, root.val), true); 
    } 
} 

Answer 23

Вот мое рекурсивное решение написано в JavaScript

function isBST(tree) { 
    if (tree === null) return true; 

    if (tree.left != undefined && tree.left.value > tree.value) { 
    return false; 
    } 

    if (tree.right != undefined && tree.right.value <= tree.value) { 
    return false; 
    } 

    return isBST(tree.left) && isBST(tree.right); 
} 

Answer 24

В 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 25

private void validateBinarySearchTree(Node node) { 
    if (node == null) return; 

    Node left = node.getLeft(); 
    if (left != null) { 
     if (left.getData() < node.getData()) { 
      validateBinarySearchTree(left); 
     } else { 
      throw new IllegalStateException("Not a valid Binary Search tree"); 
     } 
    } 

    Node right = node.getRight(); 
    if (right != null) { 
     if (right.getData() > node.getData()) { 
      validateBinarySearchTree(right); 
     } else { 
      throw new IllegalStateException("Not a valid Binary Search tree"); 
     } 
    } 
} 

Answer 26

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

""" 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 27

Один лайнер

bool is_bst(Node *root, int from, int to) { 
    return (root == NULL) ? true : 
    root->val >= from && root->val <= to && 
    is_bst(root->left, from, root->val) && 
    is_bst(root->right, root->val, to); 
} 

Довольно длинная линия, хотя.