Um die Grenze des Binärbaums zu drucken
Ich wurde in einem Interview gebeten, die Grenze des Binären Baums zu drucken. Zum Beispiel.
%Vor%Die Antwort lautet: 1, 2, 4, 8, 9, 10, 7, 3
Ich habe die folgende Antwort gegeben.
Erste Methode:
Ich habe eine Bool Variable verwendet, um das obige Problem zu lösen.
%Vor%Seine Antwort: Sie haben die Variable Bool so oft verwendet. Kannst du das lösen, ohne das zu benutzen?
Zweite Methode:
Ich habe einfach Tree Traversal verwendet, um dieses Problem zu lösen.
%Vor%Seine Antwort: Er war auch nicht glücklich mit dieser Methode. Er sagte, dass du den Baum dreimal durchqueren musst . Das ist zu viel. Geben Sie eine andere Lösung, wenn Sie welche haben.
Dritte Methode: Diesmal habe ich mich für Level Order Traversal (BFS) entschieden.
%Vor%Seine Antwort: Er schien nicht glücklich mit dieser Methode zu sein, weil diese Methode extra Gedächtnis der Ordnung O (n) braucht.
Meine Frage ist, dass Sie mir eine Methode nennen, die den Baum einzeln durchläuft, keine Bool-Variable verwendet und keinen zusätzlichen Speicher verwendet. Ist es möglich?
3 Antworten
Ich denke, das sollte den Trick machen:
%Vor% Beginnen Sie mit der Funktion traverse .
Die Null-Abfragen am Anfang jeder Methode loswerden (vermeidet einen Funktionsaufruf an jedem Ende).
Benötigt keine Bool-Variablen, verwendet einfach drei verschiedene Traversal-Methoden:
- eins für die linke Kante, Ausgabe des Knotens vor dem Durchlauf
- eine für die rechte Kante, Ausgabe des Knotens nach dem Durchlauf
- eine für alle anderen Knoten, Ausgabe des Knotens, wenn keine Geschwister vorhanden sind.
Unten ist eine rekursive Lösung in Python3 mit der Zeitkomplexität O (n). Algorithmus hier ist, die meisten Knoten von oben nach unten, Blattknoten von links nach rechts und die meisten Knoten von unten nach oben zu drucken. Das Hinzufügen boolescher Flags (isLeft,isRight) für linkes und rechtes Tree Traversal vereinfacht den Code und steuert die Zeitkomplexität von O (n).
Methode O(n) No extra space and single traversal of tree.
Ich habe die Tree Nodes in vier Arten von Knoten unterteilt
Typ 1 - & gt; Knoten, die die linke Grenze bilden (zB 8)
Geben Sie 0 - & gt; Knoten, die nicht die Grenze bilden (zB 12)
Typ 3 - & gt; Knoten, die die richtige Grenze bilden (zB 22)
Blattknoten (zB 4,10,14)
In meiner Methode mache ich nur die Rekursionsmethode des Baumdurchlaufs (gerade modifiziert), wo meine Funktion von dieser Form ist
%Vor%wo ich das
geändert habe- In meiner Rekursivfunktion müssen Knoten vom Typ 1 ihre linken Knoten bilden als Typ 1 und muss gedruckt werden, bevor sie ihre Kinder anrufen (wenn sie existieren)
- Knoten des Typs 3 müssen in umgekehrter Reihenfolge gedruckt werden. Das müssen sie sein gedruckt nach dem Anruf an ihre Kinder. Sie müssen auch ihre zuweisen rechte Kinder als Typ 3 Knoten
- Knoten des Typs 0 dürfen nicht gedruckt werden, und sie weisen ihre untergeordneten Elemente als Geben Sie 0 Knoten ein
- Blattknoten müssen nur direkt gedruckt werden und zurückgeben
Tags und Links algorithm graph-algorithm tree binary-tree binary-search-tree