Diese Frage wurde mir in einem Interview gestellt: Ich habe einen binären Baum und ich muss den gemeinsamen Vorfahren (Eltern) finden, der zwei zufällige Knoten dieses Baumes gegeben hat. Ich habe auch einen Zeiger auf den Wurzelknoten.
Meine Antwort lautet:
Durchqueren Sie den Baum separat für beide Knoten, bis Sie den erwarteten Knoten erreicht haben. Parallel beim Traversieren das Element und die nächste Adresse in einer verketteten Liste speichern. Dann haben wir zwei verkettete Listen mit uns. Versuchen Sie also, die beiden verknüpften Listen zu vergleichen, und der letzte gemeinsame Knoten in den beiden verknüpften Listen ist das übergeordnete Element.
Ich denke, dass diese Lösung richtig ist, korrigiere mich, wenn ich falsch liege. Wenn diese Lösung richtig ist, kann ich wissen, ob dies die einzige bessere Lösung für diese Aufgabe ist oder gibt es eine andere bessere Lösung als diese!
Setzen Sie einen Zeiger auf beide Zufallsknoten. Finden Sie die Tiefe jedes Knotens, indem Sie nach oben gehen und die Entfernung vom Wurzelknoten zählen. Setzen Sie den Zeiger dann erneut auf beide Knoten. Für den tieferen Knoten traversieren Sie nach oben, bis beide Zeiger die gleiche Tiefe haben. Fahren Sie dann für beide Knoten nach oben, bis die Zeiger auf denselben Knoten zeigen. Das ist der Ahnenknoten.
Mit "traverse up" bedeute ich nur, den Zeiger zum Elternknoten des aktuellen Knotens zu bewegen.
Bearbeiten, um dies zu verdeutlichen: Die Schlüsselidee ist, dass Sie, wenn beide Knoten dieselbe Tiefe haben, das gemeinsame übergeordnete Element durch einfaches Traversieren sehr schnell finden können. Also kletterst du auf den unteren, bis beide in der gleichen Tiefe sind, und dann steigst du nach oben. Entschuldigung, ich weiß nicht wirklich C oder ich würde Code schreiben, aber dieser Algorithmus sollte deine Frage beantworten.
Nochmals bearbeiten: Und meine Methode läuft in O (log (n)) Zeit und O (1) Speicher.
Eine weitere Änderung: O (log (n)) in einem ausgeglichenen Baum. Worst-Case-Leistung ist O (n) für einen unausgeglichenen Baum. Danke @DaveCahill
Ich denke, du könntest einfach für beide Knoten gleichzeitig suchen; der Punkt, an dem die Suche divergiert, ist der gemeinsame Vorfahre.
%Vor% Interessanterweise würde dieser Ansatz auf mehr als zwei Knoten skalieren (prüfen Sie, ob alle auf der linken Seite von tree stehen, usw.)
Machen Sie eine Level-Order-Traversierung, und für jeden Knoten, auf den wir treffen, überprüfen wir seine Kinder. Wenn es sich um die bereitgestellten zufälligen Knoten handelt, wird der Vorgängerknoten gefunden.
EDIT1:
Hier ist eine Gliederung
%Vor%AKTUALISIEREN
Der vorherige Algorithmus findet nur gemeinsame Eltern (direkte Vorfahren), daher würden zwei zufällig ausgewählte Knoten, die kein Kind eines gemeinsamen Elternteils sind, keine Antwort gefunden werden.
Der folgende Algorithmus findet gemeinsame Vorfahren und nicht nur Eltern.
Ich denke, der folgende Algorithmus wird funktionieren:
Machen Sie eine Postorder-Traversierung des Binärbaums, und suchen Sie nach dem Zufallsknoten 1 r1 . Wenn wir ihn finden, markieren Sie ihn in einer Statusvariablen im Zustand eins und suchen weiter Wenn der zweite Knoten gefunden wird, aktualisieren Sie die Statusvariable auf state two und beenden Sie die Suche nach mehr und zurück. Die Statusvariable sollte von jedem Knoten an seine Eltern übergeben werden (rekursiv). Der erste Knoten, der die Statusvariable in state two trifft, ist der gemeinsame Vorgänger.
Die Implementierung des Algorithmus ist wie folgt:
%Vor% Ich denke, das wird richtig funktionieren, obwohl ich immer noch die Korrektheit des Algorithmus beweisen muss. Es gibt einen Nachteil, nämlich, wenn ein Knoten ein Kind eines anderen Knotens ist, dann wird nur der Knoten gedruckt, der das übergeordnete Element des anderen ist, anstatt den übergeordneten Knoten zu drucken. If Einer der Zufallsknoten ist ein Vorfahre eines anderen Zufallsknotens. Anstatt den zufälligen Zufallsknoten zu drucken, wird der übergeordnete Knoten gedruckt. In dem Fall, in dem einer der zufälligen Knoten der Wurzelknoten ist, wird nichts gedruckt, da er immer der Vorgänger des anderen Zufallsknotens ist und daher sein gemeinsamer Vorgänger nicht existiert. In diesem speziellen Fall gibt die Funktion 0x03 in main zurück und kann erkannt werden.
Da dieser Algorithmus eine Nachorder-Traversierung durchführt, benötigt er daher O (n) Ausführungszeit und somit O (n) Speicher. Auch wenn die Suche stoppt, sobald beide Knoten gefunden werden, je flacher die Knoten sind, desto schneller endet die Suche.
AKTUALISIEREN
Hier einige Diskussionen im Modus: Wie finde ich den kleinsten gemeinsamen Vorfahren zweier Knoten in einem binären Baum?
Dieses Problem wurde sehr gut untersucht und es gibt bekannte Algorithmen, die es in linearer Zeit lösen können. Dieses Dokument beschreibt viele verschiedene Ansätze, mit denen Sie es lösen können . Es ist zwar eine Forschungsarbeit, und deshalb sind die Algorithmen ein wenig kompliziert, aber einige der Ansätze, die es beschreibt, sind tatsächlich ziemlich machbar.
Pseudocode:
%Vor%Wenn die Knoten definitiv Teil desselben Baums sind, haben sie definitiv einen gemeinsamen Vorfahren (selbst wenn es im schlimmsten Fall die Wurzel ist). So wird es immer beendet und es gibt keine Fehlerbedingung, über die man sich Sorgen machen muss.
Die erste Schleife läuft n-mal, wobei n die Tiefe von node1 ist, also ist es O (n). Die zweite Schleife läuft m-mal, wobei m in der Tiefe von node2 liegt. Das Nachschlagen in der temporären Liste ist (im schlimmsten Fall) n. Also ist die zweite Schleife O (m * n), und sie dominiert, also läuft die Funktion in O (m * n).
Wenn Sie anstelle einer Liste eine gute Datenstruktur (z. B. eine Hash-Tabelle) für den temporären Bereich verwenden, können Sie die Suche auf (typisch) 0 (1) reduzieren, ohne die Kosten für das Hinzufügen von Knoten zu temp zu erhöhen . Dies reduziert unsere Funktionszeit auf O (m).
Der Platzbedarf ist in beiden Richtungen O (n).
Da wir n und m nicht vor der Zeit wissen, lassen Sie uns die Gesamtzahl der Knoten im Baum angeben: S. Wenn der Baum ausgeglichen ist, dann sind n und m jeweils durch log_2 begrenzt (S ), so ist die Laufzeit O (log_2 (S) ^ 2). Log_2 ist ziemlich mächtig, also müsste S ziemlich groß werden, bevor ich mir Sorgen um die Potenz von 2 mache. Wenn der Baum nicht ausgeglichen ist, verlieren wir den log_2 (der Baum könnte tatsächlich zu einer verketteten Liste degenerieren). Also ist der absolut schlimmste Fall (wenn ein Knoten die Wurzel und der andere der Blatt eines vollständig entarteten Baumes ist) O (S ^ 2).
hi Dies wird den niedrigsten Wert für den Vorgängerknoten zurückgeben, wobei root of tree und val1, val2 - & gt; Datenwerte für Knoten werden übergeben
%Vor%Vorbestellen der Traversierung, sofern keine 1 des Knotens erreicht wurde, und Speichern der bisher besuchten Knoten.
Bei der Invers-Traversierung beginnen Sie, die Knoten zu speichern, wenn einer der Knoten (der beiden bereitgestellten Knoten) erfüllt ist, und speichern Sie die Liste, bis der nächste Knoten erreicht ist.
Angenommen, H und E sind zwei zufällige Knoten.
Finde den ersten Knoten in allen drei ...
Hier sind zwei Ansätze in c # (.net) (beide oben besprochen) als Referenz:
Rekursive Version des Findens von LCA im binären Baum (O (N) - wie höchstens jeder Knoten besucht wird) (Hauptpunkte der Lösung ist LCA ist (a) nur Knoten im Binärbaum, wo beide Elemente befinden sich auf jeder Seite der Teilbäume (links und rechts) ist LCA. (b) Und es spielt auch keine Rolle, welcher Knoten auf beiden Seiten vorhanden ist - zunächst habe ich versucht, diese Information zu behalten, und offensichtlich ist die rekursive Funktion so verwirrend geworden, dass ich sie, nachdem ich sie realisiert habe, sehr elegant geworden bin.
Suche nach beiden Knoten (O (N)) und Verfolgung von Pfaden (nutzt zusätzlichen Platz - so ist # 1 wahrscheinlich überlegen, auch wenn der Platz wahrscheinlich vernachlässigbar ist, wenn der Binärbaum gut ausbalanciert ist, wie zusätzlicher Speicherverbrauch sei nur in O (log (N)).
, so dass die Pfade verglichen werden (im Wesentlichen ähnlich der akzeptierten Antwort - aber die Pfade werden berechnet, indem angenommen wird, dass der Zeigerknoten nicht im Binärbaumknoten vorhanden ist)
Nur für die Vervollständigung ( nicht in Verbindung mit Frage ), LCA in BST (O (log (N))
Tests
Rekursiv:
%Vor%Dabei wird die private rekursive Version über die folgende öffentliche Methode aufgerufen:
%Vor%Lösung durch Verfolgung der Pfade beider Knoten:
%Vor%wobei FindNodeAndPath als
definiert ist %Vor%BST (LCA) - nicht verwandt (nur zur Vervollständigung als Referenz)
%Vor%Komponententests
%Vor%Tags und Links algorithm c binary-tree binary-search-tree