___ qstnhdr ___ Finden Sie, ob eine gegebene Summe über einen Pfad in einer BST existiert
___ answer13107707 ___
Ich würde, um den linken Teilbaum zu durchlaufen, und in umgekehrter Reihenfolge den rechten Teilbaum gleichzeitig durchqueren, wie merge sort funktioniert. Jedes Mal verschieben Sie den Iterator, der den Aum näher bringt. seine Reihenfolge n
___ answer13109199 ___
Sie können sicherlich alle möglichen Pfade generieren, indem Sie schrittweise summieren. Die Tatsache, dass der Baum eine BST ist, könnte Ihnen Zeit sparen, indem Sie bestimmte Summen ausgeben, obwohl ich mir nicht sicher bin, ob dies zu einer asymptotischen Geschwindigkeitserhöhung führt. Das Problem ist, dass eine unter Verwendung des linken Kinds eines gegebenen Knotens gebildete Summe nicht notwendigerweise kleiner als eine unter Verwendung des rechten Kinds gebildete Summe ist, da der Pfad für die erstere Summe viel mehr Knoten enthalten könnte. Der folgende Algorithmus funktioniert für alle Bäume, nicht nur für BSTs.
Um alle möglichen Pfade zu erzeugen, beachten Sie, dass der oberste Punkt eines Pfades speziell ist: Es ist der einzige Punkt in einem Pfad, der erlaubt (obwohl nicht erforderlich), dass beide untergeordneten Elemente im Pfad enthalten sind. Jeder Pfad enthält einen eindeutigen obersten Punkt. Daher sollte die äußere Rekursionsebene darin bestehen, jeden Baumknoten zu besuchen und alle Pfade zu generieren, die diesen Knoten als obersten Punkt haben.
%Vor%
Der obige Pseudocode meldet nur den obersten Knoten im Pfad. Der gesamte Pfad kann rekonstruiert werden, indem %code% eine Liste von Paaren %code% anstelle einer einfachen Liste von Summen zurückgibt, wobei %code% ein boolescher Wert ist, der angibt, ob der Pfad, der zum Erzeugen dieser Summe verwendet wird, vom Elternteil links geht Knoten.
Der obige Pseudocode berechnet Summenlisten mehrfach für jeden Knoten: %code% wird einmal für jeden Knoten über %code% im Baum aufgerufen und zusätzlich für %code% selbst aufgerufen. Es wäre möglich, dass %code% die Liste der Summen für jeden Knoten so memoisiert, dass sie bei nachfolgenden Aufrufen nicht neu berechnet wird, aber dies verbessert die Asymptotik nicht: es wird nur O (n) benötigt, um a zu erzeugen Liste von n Summen unter Verwendung der einfachen Rekursion, und das Ändern dieser in O (1) ändert nicht die gesamte Zeitkomplexität, da die gesamte Liste von Summen, die durch irgendeinen Aufruf von %code% erzeugt wird, sowieso vom Aufrufer gelesen werden muss das erfordert O (n) time. BEARBEITEN: Wie von Evgeny Kluev aufgezeigt, verhält sich %code% tatsächlich wie eine Mergesorte, dh O (nlog n), wenn der Baum perfekt ausgeglichen ist und O (n ^ 2) wenn es ein einzelner Pfad ist. Memorization wird also tatsächlich eine asymptotische Leistungsverbesserung bewirken.
Es ist möglich, die temporären Listen von Summen zu entfernen, indem %code% in ein iteratorähnliches Objekt umgeordnet wird, das die Listenverschmelzung träge durchführt und abgefragt werden kann, um die nächste Summe in aufsteigender Reihenfolge abzurufen. Dies würde auch bedeuten, dass ein %code% erstellt wird, das dasselbe tut, aber Summen in absteigender Reihenfolge abruft und dies anstelle von %code% verwendet. Dadurch wird die Komplexität des Algorithmus auf O (n) reduziert, wobei n die Anzahl der Knoten in der Struktur ist, da jedes Iteratorobjekt konstanten Platz benötigt (Zeiger auf die linken und rechten untergeordneten Iteratorobjekte plus einen Platz zum Aufzeichnen der letzte Summe) und es kann höchstens einen pro Baumknoten geben.
___ tag123binarytree ___ Baumdatenstrukturen, in denen jeder Knoten höchstens zwei untergeordnete Knoten hat.
___ tag123algorithm ___ Ein Algorithmus ist eine Folge wohldefinierter Schritte, die eine abstrakte Lösung für ein Problem definieren. Verwenden Sie dieses Tag, wenn sich Ihr Problem auf den Algorithmusentwurf bezieht.
___ antwort13110019 ___
Nicht der schnellste, aber einfachste Ansatz wäre die Verwendung von zwei verschachtelten Tiefensuche.
Verwenden Sie die normale Tiefensuche, um den Startknoten zu erhalten. Verwenden Sie die zweite, modifizierte Version der Tiefensuche, um die Summen für alle Pfade ab diesem Knoten zu überprüfen.
Die zweite Tiefensuche unterscheidet sich von der normalen Tiefensuche zuerst in zwei Details:
- Es behält die aktuelle Pfadsumme bei. Sie fügt der Summe jedes Mal einen Wert hinzu, wenn dem Pfad ein neuer Knoten hinzugefügt wird, und entfernt den Wert aus der Summe, wenn ein Knoten entfernt wird.
- Es überquert Kanten des Weges von der Wurzel zum Startknoten nur in entgegengesetzter Richtung (rote Kanten im Diagramm). Alle anderen Kanten werden wie üblich in der richtigen Richtung durchlaufen (schwarze Kanten im Diagramm). Um Kanten in entgegengesetzter Richtung zu durchlaufen, verwendet es entweder "Eltern" -Zeiger der ursprünglichen BST (falls es welche gibt) oder guckt in den Stapel der ersten Tiefensuche, um diese "Eltern" -Zeiger zu erhalten.
Zeitkomplexität jedes DFS in O (N), so ist die gesamte Zeitkomplexität O (N 2 ). Platzanforderungen sind O (N) (Platz für beide DFS-Stapel). Wenn die ursprüngliche BST "Eltern" -Zeiger enthält, sind die Platzanforderungen O (1) ("Eltern" -Zeiger ermöglichen das Durchqueren des Baums in jeder Richtung ohne Stapel).
Ein anderer Ansatz basiert auf den Ideen von j_random_hacker und robert king (Listen von Summen pflegen, zusammenführen und dann zusammenführen). Es verarbeitet den Baum in Bottom-Up-Manier (ausgehend von Blättern).
Verwenden Sie DFS, um einen Blattknoten zu finden. Dann gehe zurück und finde den letzten Verzweigungsknoten, der ein Grand -...- Großelternteil dieses Blattknotens ist. Dies ergibt eine Kette zwischen Ast- und Astknoten. Verarbeite diese Kette:
%Vor%
Setzen Sie DFS fort und suchen Sie nach anderen Blattketten. Wenn zwei Ketten vom gleichen Knoten gefunden werden, denen möglicherweise eine andere Kette vorangeht (rote und grüne Ketten im Diagramm, gefolgt von einer blauen Kette), verarbeiten Sie diese Ketten:
%Vor%
Machen Sie dasselbe, wo immer zwei Listen von Summen oder eine Kette und eine Liste von Summen Nachkommen desselben Knotens sind. Dieser Prozess kann fortgesetzt werden, bis eine einzelne Liste von Summen, die zum Stammknoten gehören, verbleibt.
___ answer13107477 ___
Gibt es irgendwelche Komplexitätsbeschränkungen?
Wie Sie gesagt haben: " einfach, wenn ein Pfad" root to leaf "bedeutet, oder einfach, wenn der Pfad einen Teil eines Pfades von root zu leaf bedeutet, der nicht den root oder das leaf enthalten darf ".
Sie können das Problem auf diese Anweisung reduzieren, indem Sie den Stamm jedes Mal auf einen anderen Knoten setzen und die Suche n-mal durchführen.
Das wäre ein direkter Ansatz, nicht sicher, ob optimal.
Bearbeiten : Wenn der Baum unidirektional ist, könnte etwas dieser Art funktionieren (Pseudocode):
%Vor%
Wahrscheinlich viele Fehler hier, aber hoffentlich klärt es die Idee.
___ tag123binarysearchtree ___ Ein binärer Suchbaum ist eine Datenstruktur, die aus einem Wurzelknoten mit linken und rechten Kindknoten besteht. Der linke Knoten und alle seine Nachkommen haben kleinere Werte als der Stammknoten, während der rechte Knoten und alle seine Nachkommen größere Werte als der Stammknoten haben. Die Kinder des Wurzelknotens folgen demselben Muster. Dies gibt uns einen Baum, der aus geordneten Elementen besteht.
___ qstntxt ___
Die Frage ist, ob eine gegebene Summe über irgendeinen Pfad in einer BST existiert. Die Frage ist verdammt einfach, wenn ein Pfad von Blatt zu Blatt geht, oder einfach, wenn der Pfad einen Teil eines Pfades von der Wurzel bis zum Blatt bedeutet, der nicht die Wurzel oder das Blatt enthalten kann. Aber es wird hier schwierig, weil ein Pfad sowohl das linke als auch das rechte Kind eines Knotens umfassen kann. Zum Beispiel existiert in der gegebenen Figur eine Summe von 132 über dem eingekreisten Pfad. Wie kann ich die Existenz eines solchen Pfades finden? Die Verwendung von Hash zum Speichern aller möglichen Summen unter einem Knoten ist verpönt!
___