Ich wurde diese Frage in einem Interview gestellt und es kostete mich buchstäblich einen Job: P Der Interviewer hat gefragt, dass Sie die Wurzel für einen Baum erhalten und dass Sie den Stamm an den kopierten Baum zurückgeben müssen, aber die Kopie sollte iterativ gemacht werden. Ich paste meinen Code hier, ich schrieb das gleiche dort, und es funktioniert gut. Ich habe dies zunächst mit zwei Stapeln gemacht, die der Interviewer sagte, dass er nicht mochte, dann tat ich es auf die folgende Weise. Der Interviewer war irgendwie unglücklich über mich, eine andere Struktur zu verwenden, die den Zeiger auf den ursprünglichen und letzten Baum hält (Verweiscode). Ich frage mich, gibt es eine andere, bessere Möglichkeit, dies zu tun?
%Vor%Wenn Sie in jedem Knoten Elternzeiger haben dürfen, brauchen Sie nicht einmal den Stack:
Gehen Sie den ursprünglichen Baum und den Baum, den Sie erstellen, parallel durch. Wenn der aktuelle Knoten in der ursprünglichen Struktur ein untergeordnetes untergeordnetes Element aufweist, der Knoten in der zu erstellenden Struktur jedoch nicht, erstellen Sie ihn und fahren Sie nach links ab. Ähnlich mit richtigen Kindern. Wenn keine der Bedingungen zutrifft, gehen Sie nach oben.
Im Code (C #):
%Vor%zwei Ideen:
Sie benötigen entweder einen Stack oder übergeordnete Links, um den Eingabebaum zu durchlaufen (afaict). also nehmen wir an, dass der Interviewer mit einem von denen glücklich sein würde. Was bleibt zu vereinfachen?
In Ihrem Code durchlaufen Sie auch die Kopie und speichern ihre Knoten parallel zu Ihrem Original. Stattdessen können Sie dem Stamm der Kopie einfach Knoten hinzufügen. Solange du das Traversieren des Originals richtig gewählt hast, erhältst du die gleiche Struktur.
und es ist nicht schwer zu erkennen, dass das Pre-Order-Traversal dies tun würde (unter der Annahme, dass bei der Addition kein Re-Balancing stattfindet).
, so dass Sie Ihre Kopie in Form von Pre-Order Traversal plus einfachen Zusatz zum Kopierstamm schreiben können. das würde einfacheren Code geben und / oder die Wiederverwendung erlauben, auf Kosten von weniger effizient (Sie haben O (nlog (n)) zusätzliche "Hops", um die richtigen Stellen in Ihrer Kopie beim Einfügen zu finden).
Für unveränderliche Knoten müssen Sie nur die Wurzel kopieren (dies ist der normale funktionale Stil).
Mein Bauchgefühl ist, dass (1) möglicherweise das ist, wonach er gesucht hat, wenn man den Bezug auf "Eigenschaften eines Baumes" betrachtet.
Eine Methode ohne Rekursion wäre, durch jeden Knoten zu gehen, und wenn der Knoten eine rechte Verzweigung enthält, drücke diesen rechten Knoten auf einen Stapel. Wenn Ihnen die Knoten entlang Ihres Pfades ausgehen (folgen Sie nur den Knoten mit den linken Zweigen), blenden Sie den obersten Knoten vom Stapel und folgen Sie ihm mit den gleichen Regeln (drücken Sie rechts, dann folgen Sie der linken Seite). Wiederholen Sie diese Schleife, bis der Stapel leer ist. Dies sollte nur einen einzelnen Stapel erfordern.
Bearbeiten: Haben Sie den Interviewer gefragt, nach welcher Methode er gesucht hat? Wenn nicht, sollten Sie auf eine Weise, die Ihre Bereitschaft, neue Dinge zu lernen, vorgeschlagen haben, und Sie sollten versucht haben, es zu einem zweiseitigen Dialog zu machen. Ich bin mir sicher, dass du diese Bereitschaft hast, neue Dinge zu lernen (oder du hättest es hier nicht veröffentlicht), aber hat dein Interviewer das gewusst? Denken Sie daran - Interviewer suchen im Allgemeinen nicht nach einer bestimmten Antwort auf die Dinge, sondern sie versuchen eher, Ihren Lösungsansatz zu bewerten, und zwar nicht nur in technischer Hinsicht. Wenn Sie nicht so vorgingen, haben Sie es dem Interviewer unmöglich gemacht zu denken, dass Sie nicht alles wissen, aber lernen können und eine großartige Ergänzung für Ihr Team darstellen.
Betrachten Sie unter Baum:
%Vor%Wenn Sie nun auf der Grundlage von BFS ein Array von Knoten erstellen (Array wird für einen schnelleren Zugriff verwendet), wäre dies wie folgt:
Knotengruppe: 10 20 30 40 50 N N N N 60 70 N N N N
Index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Bitte beachten Sie, dass die Indizierung für eine einfachere Berechnung auf 1 basiert, und Kinder von Blattknoten werden als N für NULL bezeichnet.
Wenn Sie nun bemerken, dass für einen Knoten an einem Index i sein linkes Kind am Index 2 * i und sein rechtes Kind am Index 2 * i + 1 ist. Dies ist durch die Eigenschaft von ein richtiger Binärbaum.
Nun um den Binärbaum nicht rekursiv zu kopieren.
Machen Sie unten während der aktuellen & lt; = Größe des Arrays von Knoten
a. Erstelle einen neuen Knoten (Eltern)
b. Weisen Sie den Wert parent- & gt; val vom aktuellen Knoten zu.
c. Ersetzen Sie den ursprünglichen Knoten im aktuellen (Index) durch den neuen Knoten. // Dieser Schritt ist in der Lage, die neuen Knoten zu durchlaufen.
d. Erstellen Sie einen neuen Knoten, weisen Sie ihn Eltern- & gt; links zu und weisen Sie den Wert aus Lindex = 2 * aktuell zu.
e. Ersetzen Sie den ursprünglichen Knoten in Lindex durch den neuen Knoten.
f. Erstellen Sie einen neuen Knoten, weisen Sie Parent- & gt; rechts zu und weisen Sie den Wert aus Rindex = 2 * current + 1 zu.
e. Ersetzen Sie den ursprünglichen Knoten in Rindex durch den neuen Knoten.
f. Inkrementiere den Strom um 1.
Kommen wir nun zu der Zeitkomplexität,
Da wir im Array auch NULL-Kinder von externen Knoten berücksichtigt haben, müssen wir die Gesamtgröße des Arrays berechnen.
Wenn die Anzahl der Knoten im ursprünglichen Baum n ist, ist die Anzahl der externen Knoten eines Binärbaums durch die Eigenschaft des Binärbaums immer 1 mehr als die Anzahl der internen Knoten
%Vor%Da wir im gesamten Algorithmus das gesamte Array durchlaufen haben, ist die Zeitkomplexität dieses Ansatzes O (n).