wake-up-neo.com

Finden, ob ein binärer Baum ein binärer Suchbaum ist

Heute hatte ich ein Interview, in dem ich gebeten wurde, ein Programm zu schreiben, das einen Binärbaum aufnimmt und true zurückgibt, wenn es sich auch um einen Binärsuchbaum handelt, der ansonsten false ist.

Mein Ansatz1: Führe eine geordnete Durchquerung durch und speichere die Elemente in O(n) Zeit. Nun durchsuche das Array/die Liste der Elemente und überprüfe, ob das Element bei i istth Index ist größer als Element bei (i + 1)th Index. Wenn eine solche Bedingung auftritt, geben Sie false zurück und brechen Sie die Schleife ab. (Dies benötigt O(n) Zeit.) Am Ende wird true zurückgegeben.

Aber dieser Herr wollte, dass ich eine effiziente Lösung anbiete. Ich habe versucht, aber ich war nicht erfolgreich, da ich jeden Knoten überprüfen muss, um festzustellen, ob es sich um eine BST handelt.

Außerdem wies er mich an, über Rekursion nachzudenken. Mein Ansatz 2: Ein BT ist ein BST, wenn für einen beliebigen Knoten N N-> left <N und N-> right> N ist und der geordnete Nachfolger des linken Knotens von N kleiner ist als N und der geordnete Nachfolger des rechten Knotens von N ist größer als N und die linken und rechten Teilbäume sind BSTs.

Aber das wird kompliziert und die Laufzeit scheint nicht gut zu sein. Bitte helfen Sie, wenn Sie eine optimale Lösung kennen.

33
dharam

Es ist ein ziemlich bekanntes Problem mit der folgenden Antwort:

public boolean isValid(Node root) {
     return isValidBST(root, Integer.MIN_VALUE,
          Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int l, int h) {
     if(node == null)
         return true;
     return node.value > l 
         && node.value < h
         && isValidBST(node.left, l, node.value)
         && isValidBST(node.right, node.value, h);
}

Der rekursive Aufruf stellt sicher, dass sich die Teilbaumknoten im Bereich seiner Vorfahren befinden, was wichtig ist. Die Laufzeitkomplexität ist O(n), da jeder Knoten einmal untersucht wird.

Die andere Lösung wäre, eine Inorder-Traversierung durchzuführen und zu prüfen, ob die Sequenz sortiert ist, zumal Sie bereits wissen, dass ein Binärbaum als Eingabe bereitgestellt wird.

78
Dhruv Gairola

Die Antwort von @Dhruv ist gut. Darüber hinaus ist hier eine andere Lösung, die in O(n) Zeit arbeitet.
Wir müssen bei diesem Ansatz den vorherigen Knoten verfolgen. Bei jedem rekursiven Aufruf überprüfen wir die vorherigen Knotendaten mit den aktuellen Knotendaten. Wenn die aktuellen Knotendaten kleiner als die vorherigen sind, geben wir false zurück

int isBST(node* root) {
  static node* prev  = NULL;

  if(root==NULL)
    return 1;

  if(!isBST(root->left))
    return 0;

  if(prev!=NULL && root->data<=prev->data)
    return 0;

  prev = root;
  return isBST(root->right);
}
7
AgentX
boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max){
  if(node == null){
    return true;
  }

  boolean left  = isBinarySearchTree(node.getLeft(), min, node.getValue());
  boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

  return left && right && (node.getValue()<max) && (node.getValue()>=min);      
}

Kommentare sind eingeladen. Vielen Dank.

1
Trying

Ich denke, dass der zweite Ansatz richtig ist. Der Baum kann rekursiv durchlaufen werden. Bei jeder Iteration können die unteren und oberen Grenzen des aktuellen Teilbaums gespeichert werden. Wenn wir den Teilbaum mit root x überprüfen möchten und die Grenzen für den Teilbaum l und h sind, müssen wir nur l <= x <= h und den linken Teilbaum mit den Grenzen l und x und rechts überprüfen eine mit den Grenzen x und h.

Dies wird O(n) Komplexität haben, da wir von der Wurzel ausgehen und jeder Knoten nur einmal als Wurzel eines Teilbaums geprüft wird. Außerdem benötigen wir O(h) Speicher für rekursive Aufrufe, wobei h die Höhe des Baums ist.

0
fdermishin