Diese Frage hat hier bereits eine Antwort:

Heute hatte ich ein Interview, in dem ich gebeten wurde, ein Programm zu schreiben, das einen Binary Tree nimmt und true zurückgibt, wenn es auch ein Binary Search Tree ist, der ansonsten false ist.

Mein Ansatz1: Führe eine geordnete Durchquerung durch und speichere die Elemente in O (n) Zeit. Scannen Sie nun das Array / die Liste der Elemente und prüfen Sie, ob das Element bei ith 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 es versucht, war aber erfolglos. Um festzustellen, ob es sich um eine BST handelt, muss jeder Knoten überprüft werden.

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.