Wie validieren Sie einen binären Suchbaum?

Eigentlich ist das der Fehler, den jeder in einem Interview macht. 

Leftchild muss gegen (minLimitof node, node.value) geprüft werden

Rightchild muss gegen (node.value, MaxLimit des Knotens) geprüft werden

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

Eine andere Lösung (wenn Leerzeichen keine Einschränkung ist): Führen Sie eine Inorder-Durchquerung des Baums durch und speichern Sie die Knotenwerte in einem Array. Ist das Array in sortierter Reihenfolge, ist es ansonsten keine gültige BST.

"Validieren" eines binären Suchbaums bedeutet, dass Sie überprüfen, ob tatsächlich alle kleineren Elemente auf der linken und große Elemente auf der rechten Seite vorhanden sind. Im Wesentlichen wird geprüft, ob es sich bei einem binären Baum um einen binären SuchBaum handelt.

Die beste Lösung, die ich gefunden habe, ist O(n) und benötigt keinen zusätzlichen Platz. Es ist ähnlich wie inorder-Durchquerung, aber anstatt es in Array zu speichern und zu prüfen, ob es sortiert ist, können wir eine statische Variable verwenden und überprüfen, während inorder durchquert wird, ob Array sortiert ist.

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

Iterative Lösung mit Inorder-Traversal.

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

Hier ist meine Lösung in 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)))

Da das In-Order-Durchlaufen einer BST eine Sequenz ohne Abnahme ist, können Sie diese Eigenschaft verwenden, um zu beurteilen, ob ein binärer Baum BST ist oder nicht. Durch die Verwendung von Morris Traversal und der Aufrechterhaltung des pre-Knotens könnten wir eine Lösung in O(n) Zeit und O(1) Space Komplexität erhalten. Hier ist mein Code

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

Hier ist meine Antwort in Python, es hat alle Eckpunkte angesprochen und in Hackerrank-Website getestet

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

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

Ich habe diese Frage kürzlich in einem Telefoninterview bekommen und habe mich mehr damit abgemüht, als ich hätte haben sollen. Ich versuchte, Minimums und Maximums in Kinderknoten zu verfolgen, und ich konnte mein Gehirn einfach nicht um die verschiedenen Fälle unter dem Druck eines Interviews wickeln.

Nachdem ich letzte Nacht beim Einschlafen darüber nachgedacht hatte, stellte ich fest, dass es so einfach ist, den letzten Knoten zu verfolgen, den Sie während einer Inorder-Durchquerung besucht haben. In 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;
}

"Es ist besser, zuerst eine Invariante zu definieren. Hier ist die Invariante - alle zwei aufeinanderfolgenden Elemente der BST im In-Order-Durchlauf müssen in strikt aufsteigender Reihenfolge ihres Auftretens sein (können nicht gleich sein, immer in der Reihenfolge.) traversal). Die Lösung kann also nur ein einfacher Durchlauf in der Reihenfolge sein, wobei der zuletzt besuchte Knoten erinnert und der aktuelle Knoten mit dem zuletzt besuchten Knoten mit '<' (oder '>') verglichen wird. "

In Java und Zulassen von Knoten mit gleichem Wert in einem der Unterbäume:

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

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

Einzeiler

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

Ziemlich lange Schlange. 

Rekursion ist einfach, aber der iterative Ansatz ist besser. Es gibt eine iterative Version, die jedoch viel zu komplex ist. Hier ist die beste -Lösung in c++, die Sie überall finden können:

Dieser Algorithmus läuft in O(N) Zeit und benötigt O(lgN) Platz.

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

Es folgt die Java-Implementierung der BST-Validierung, bei der wir den Baum in der Reihenfolge DFS durchlaufen und False zurückgeben, wenn wir eine Zahl erhalten, die größer als die letzte Zahl ist.

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

Rekursive Lösung:

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)

    }

Inspiriert von http://www.jiuzhang.com/solutions/validate-binary-search-tree/

Es gibt zwei allgemeine Lösungen: Durchqueren und Teilen & & Erobern.

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

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

Funktioniert gut :)

Iterative Lösung. 

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

Python-Implementierungsbeispiel. In diesem Beispiel werden Typanmerkungen verwendet. Da sich die Node-Klasse jedoch selbst verwendet, müssen wir als erste Zeile des Moduls Folgendes angeben:

from __future__ import annotations

Andernfalls erhalten Sie einen name 'Node' is not defined-Fehler. In diesem Beispiel wird auch die Datenklasse als Beispiel verwendet. Um zu prüfen, ob es sich um eine BST handelt, wird Rekursion zum Überprüfen der Werte für den linken und rechten Knoten verwendet.

"""Checks if Binary Search Tree (BST) is balanced"""

from __future__ import annotations
import sys
from dataclasses import dataclass

MAX_KEY = sys.maxsize
MIN_KEY = -sys.maxsize - 1


@dataclass
class Node:
    value: int
    left: Node
    right: Node

    @property
    def is_leaf(self) -> bool:
        """Check if node is a leaf"""
        return not self.left and not self.right


def is_bst(node: Node, min_value: int, max_value: int) -> bool:
    if node.value < min_value or max_value < node.value:
        return False
    Elif node.is_leaf:
        return True

    return is_bst(node.left, min_value, node.value) and is_bst(
        node.right, node.value, max_value
    )


if __== "__main__":
    node5 = Node(5, None, None)
    node25 = Node(25, None, None)
    node40 = Node(40, None, None)
    node10 = Node(10, None, None)

    # balanced tree
    node30 = Node(30, node25, node40)
    root = Node(20, node10, node30)
    print(is_bst(root, MIN_KEY, MAX_KEY))

    # unbalanced tree
    node30 = Node(30, node5, node40)
    root = Node(20, node10, node30)
    print(is_bst(root, MIN_KEY, MAX_KEY))

• Die Funktion iterative prüft iterativ, ob der angegebene Baum ein binärer Suchbaum ist. 
• Die Funktion recurse prüft rekursiv, ob der angegebene Baum ein binärer Suchbaum ist oder nicht. 
• In iterative Funktion verwende ich bfs zur Überprüfung von BST.
• In recurse Funktion verwende ich dfs zur Überprüfung von BST.
• Beide Lösungen haben eine zeitliche Komplexität von O(n)
• Die Lösung iterative hat einen Vorteil gegenüber der Lösung recurse und iterative die Lösung bricht früh ab.
• Sogar die Funktion recurse kann durch den globalen Flag-Wert auf frühes Anhalten optimiert werden. 
• Die Idee beider Lösungen ist, dass das linke Kind im Bereich von -infinity bis zum Wert seines übergeordneten Knotens liegen sollte, der der Wurzelknoten ist
• Das rechte untergeordnete Element sollte innerhalb des Bereichs von + unendlich bis zum Wert des übergeordneten Knotens liegen, der der Wurzelknoten ist

• Und vergleichen Sie weiterhin den aktuellen Wert des Knotens innerhalb des Bereichs. Wenn sich der Wert eines Knotens nicht im Bereich befindet, geben Sie False zurück

  class Solution:
      def isValidBST(self, root):
          """
          :type root: TreeNode
          :rtype: bool
          """
          return self.iterative(root)
          # return self.recurse(root, float("inf"), float("-inf"))
  
      def iterative(self, root):
          if not root:
              return True
  
          level = [[root, -float("inf"), float("inf")]]
  
          while level:
              next_level = []
  
              for element in level:
                  node, min_val, max_val = element
                  if min_val<node.val<max_val:
                      if node.left:
                          next_level.append([node.left, min_val, node.val])
                      if node.right:
                          next_level.append([node.right, node.val, max_val])
                  else:
                      return False
              level = next_level
  
          return True
  
      def recurse(self, root, maxi, mini):
          if root is None:
              return True
  
          if root.val < mini or root.val > maxi:
              return False
  
          return self.recurse(root.left, root.val-1, mini) and self.recurse(root.right, maxi, root.val+1)
  

Hier ist eine Lösung in Java aus der Algorithmusklasse von sedgewick ..__ Überprüfen Sie die vollständige BST-Implementierung hier

Ich habe einige erklärende Kommentare hinzugefügt

private boolean isBST() {
    return isBST(root, null, null);

}

private boolean isBST(Node x, Key min, Key max) {
    if (x == null) return true;
    // when checking right subtree min is key of x's parent
    if (min != null && x.key.compareTo(min) <= 0) return false;
    // when checking left subtree, max is key of x's parent
    if (max != null && x.key.compareTo(max) >= 0) return false;
    // check left subtree and right subtree
    return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);

}

Ich habe eine Lösung geschrieben, um inorder Traversal BST zu verwenden, und zu überprüfen, ob die Knoten die Reihenfolge für den Raum O(1) und die Zeit O(n) erhöhen. TreeNode predecessor ist der vorige Knoten. Ich bin nicht sicher, ob die Lösung richtig ist oder nicht. Weil das inorder Traversal keinen ganzen Baum definieren kann.

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;

}

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

Dies funktioniert bei Duplikaten. 

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

Dies funktioniert auch für int.min- und int.max-Werte mit Nullable-Typen. 

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

Um herauszufinden, ob BT für jeden Datentyp BST ist, müssen Sie den folgenden Ansatz verwenden: 1. rekursive Funktion bis zum Ende des Blattknotens mit Inorder-Durchlauf aufrufen 2. Bauen Sie Ihre minimalen und maximalen Werte selbst auf.

Das Baumelement muss kleiner oder größer als der definierte Operator sein. 

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