BST aus zwei unsortierten Array

• Nimm das erste Element - Dies ist die Wurzel (im obigen Fall ist es 2)
• Alle Elemente, die kleiner als das Stammelement sind, sollten in beiden Arrays in der gleichen Reihenfolge angezeigt werden
  • Im obigen Beispiel sind 0 und 1 die Elemente, die kleiner sind als die Wurzelelemente.
  • Im ersten Array ist die Reihenfolge 1, 0
  • Die gleiche Reihenfolge wird im zweiten Array beibehalten. So bilden beide die gleiche Struktur

• Alle Elemente, die größer als das Wurzelelement sind, sollten in beiden Arrays in der gleichen Reihenfolge angezeigt werden

  • Im obigen Beispiel ist 4 das einzige Element, das größer als 2 ist. Es erscheint in beiden Arrays. Und daher erzeugen beide Arrays BST, die strukturell gleich sind.

• Und natürlich ist die allererste Bedingung, dass beide Arrays die gleichen Elemente enthalten sollen, aber in anderer Reihenfolge.

Daher kann dies in linearer Zeit gelöst werden.

Pseudocode wäre wie folgt:

Ich stimme der Idee zu, die Peter und Algorist beschrieben haben. Aber ich glaube, dass die Unterbäume jedes Knotens (dargestellt durch die Anordnung kleiner als dieser Knoten und die Anordnung größer als sie) auf diese Art und Weise untersucht werden müssen. Zum Beispiel ergeben 621407 und 621047 die gleiche BST, aber 624017 nicht. Die Funktion kann rekursiv geschrieben werden.

Beispielcode hinzugefügt:

Funktionspartition ist die gleiche, die Sie in Quicksort verwenden. Offensichtlich ist T (n) = 2T (n / 2) + O (n), was zu der Zeitkomplexität T (n) = O (nlogn) führt. Wegen der Rekursion ist die Raumkomplexität O (logn)

Sie können die detaillierte Erläuterung zum Vergleich von zwei Binärbäumen (nicht nur BST) unter prüfen, ob zwei Binärbäume gleich sind . Es ist einfach, BST aus den Arrays zu erstellen und dann den Algorithmus in den genannten Fragen auszuführen.

IMO, Sie können ein Array sortieren und eine Binärsuche vom zweiten Array zum sortierten Array durchführen, stellen Sie jedoch sicher, dass Sie jedes Element verwenden. Es kostet dich mlog.

Überprüfen Sie, ob es die gleiche bst erzeugt?

Ja.

Beginnen Sie, das erste Element als root zu verwenden und die Zahl, die größer als root ist, nach rechts und kleiner als root nach links zu halten.

Wenn Sie dem obigen Verfahren folgen, werden Sie feststellen, dass beide Bäume identisch sind.

Der Punkt kann sein, Permutationen der Teilsegmente eines Arrays mit den jeweiligen Teilsegmenten des anderen Arrays zu vergleichen (think level order):

beginnend mit dem ersten Element im Array, für i = 0 bis einige n, gruppieren Sie die Elemente in Mengen von 2 ^ i

2 ^ 0 = 1: Das erste Element ist die Wurzel - muss beide Arrays starten: [50].

2 ^ 1 = 2: Jede Permutation der nächsten 2 Elemente ist in Ordnung:

2 ^ 2 = 4: Jede Permutation der nächsten 4 Elemente ist in Ordnung:

2 ^ 3 = 8: Jede Permutation der nächsten 8 Elemente ist in Ordnung:

gehen Sie zu 2 ^ n, bis die Arrays leer sind. entsprechende Subsegmente müssen die gleiche Anzahl von Elementen haben.

1) Sortieren Sie das Array mithilfe von Zählen oder Radix-Sortierung.

2) Erstellen Sie einen Baum mit unserem sortierten Array und einem unsortierten Array (zum Überprüfen des Anzeigenauftrags). Es wird die Struktur des Baumes erhalten.

3) Vergleichen Sie beide Bäume.

Alles kann in linearer Zeit ausgeführt werden - O (n).

Code: