Code-Herausforderung: Binärbaumalgorithmen in Swift verstehen
Herausforderung: Ermitteln Sie bei einem * nicht leeren * Binärbaum die maximale Pfadsumme. Für dieses Problem wird ein Pfad als eine beliebige Folge von Knoten von einem Startknoten zu einem beliebigen Knoten im Baum entlang der Eltern-Kind-Verbindungen definiert. Der Pfad muss mindestens einen Knoten enthalten und muss nicht durch die Wurzel gehen:
Example #1:
Input:
4
/ \
5 6
Output: 15
Beispiel #2:
Input:
-10
/ \
9 20
/ \
15 7
Output: 42
Die Herausforderung
Wie der Name schon sagt, ist ein binärer Baum eine beliebte Art von baumbasierter Datenstruktur. Um ihre Zeit- und Raumeffizienz zu unterstützen, werden Bäume häufig durch einen Schlüssel und zwei oder mehr Blattknoten dargestellt, ähnlich den folgenden Strukturen:
As one may guess, recursion is also a common property of tree-based structures. Obwohl die meisten rekursiven Funktionen in realen Anwendungen verpönt sind, ermöglichen Bäume bestimmte Effizienzen, da jeder Blattknoten auch einen anderen Baum darstellen kann:
Wenn Bäume nicht richtig verstanden werden, können sie zu Verwirrung und zusätzlicher Komplexität führen. Um unsere Code-Herausforderung zu lösen, müssen wir eine konsistente Methode für die Navigation in unserem Baum entwickeln und alle möglichen Permutationen vergleichen.
Lassen Sie uns unsere Ideen visualisieren, bevor wir sie in Code umwandeln. Zu Beginn werden wir uns zunächst mit der Navigation im Baum befassen. Da Baumstrukturen eine zusätzliche Konzepteigenschaft von *depth * enthalten, werden einfache Techniken wie die schnelle Aufzählung normalerweise nicht angewendet. Stattdessen können wir bestimmte Traversal-Algorithmen wie die Tiefensuche oder die Breitensuche (z. B. DFS bzw. BFS) verwenden. Obwohl das Thema BFS detailliert genug für eine neue Diskussion ist, können wir daraus schließen, dass dies der normale Weg wäre, eine solche Struktur zu durchqueren. Da wir jedoch mit einem Binärbaum arbeiten, können wir bestimmte algorithmische Effizienzen anwenden, um den Durchlaufprozess zu verkürzen.
Also, was ist ein Binärbaum? Im Wesentlichen handelt es sich um ein Standardarray, das als Baum visualisiert wird. In diesem Fall liegt der Schwerpunkt auf den Visualisierungsaspekten, da dies die Navigation in der Struktur beeinflusst. Beispielsweise können für jeden Knoten die untergeordneten Knoten des linken und rechten Blattes mithilfe dieser einfachen Formeln berechnet werden:
Wie bereits erläutert, funktionieren diese Formeln, da die zugrunde liegende Struktur für unseren Baum ein Array ist. Dies unterscheidet sich von anderen Strukturen wie einem B-Baum, Trie oder Graph, wo man eine bestimmte benutzerdefinierte Datenstruktur anwenden würde, um ein Modell darzustellen.
Vergleiche anstellen
Da unser Binärbaum eigentlich nichts anderes als ein Array ist, können wir tatsächlich eine grundlegende Aufzählung verwenden, um alle Werte zu durchlaufen. Wir wenden jedoch unsere Formeln an, um unsere untergeordneten Blattknoten zu bestimmen. Einmal etabliert, können wir die Summen jedes Unterbaums mit einer einfachen Form der Memoisierung verfolgen (z. dynamische Programmierung).
Leave a Reply