Aufgabe
Geben Sie angesichts der Vor- und Nachbestellungsdurchläufe eines vollständigen Binärbaums dessen Durchlauf in der Reihenfolge zurück.
Die Durchläufe werden als zwei Listen dargestellt, die beide n unterschiedliche positive ganze Zahlen enthalten, die jeweils einen Knoten eindeutig identifizieren. Ihr Programm kann diese Listen verwenden und den resultierenden Durchlauf in der Reihenfolge unter Verwendung eines angemessenen E / A-Formats ausgeben.
Sie können davon ausgehen, dass die Eingabe gültig ist (dh, die Listen repräsentieren tatsächlich Durchquerungen eines Baums).
Dies ist Code-Golf , also gewinnt der kürzeste Code in Bytes.
Definitionen
Ein vollständiger Binärbaum ist eine endliche Struktur von Knoten , die hier durch eindeutige positive ganze Zahlen dargestellt wird.
Ein vollständiger Binärbaum ist entweder ein Blatt , das aus einem einzelnen Knoten besteht :
1
Oder ein Zweig , der aus einem Knoten mit zwei Teilbäumen (als linker und rechter Teilbaum bezeichnet ) besteht, von denen jeder wiederum ein vollständiger Binärbaum ist:
1 / \ … …
Hier ist ein vollständiges Beispiel für einen vollständigen Binärbaum:
6
/ \
3 4
/ \ / \
1 8 5 7
/ \
2 9
Das Durchlaufen eines vollständigen Binärbaums vor der Bestellung wird rekursiv wie folgt definiert:
- Die Vorbestellungsdurchquerung eines Blattes, das einen Knoten n enthält, ist die Liste [ n ].
- Die Vorbestellungsdurchquerung eines Zweigs , der einen Knoten n und Unterbäume (L, R) enthält, ist die Liste [ n ] + Vorbestellung ( L ) + Vorbestellung ( R ), wobei + der Listenverkettungsoperator ist.
Für den obigen Baum ist das [6, 3, 1, 8, 2, 9, 4, 5, 7] .
Das Durchlaufen eines vollständigen Binärbaums nach der Bestellung wird rekursiv wie folgt definiert:
- Die Nachbestellung eines Blattes, das einen Knoten n enthält, ist die Liste [ n ].
- Die Nachbestellungsdurchquerung eines Zweigs , der einen Knoten n und Unterbäume ( L , R) enthält, ist die Liste Nachbestellung ( L ) + Nachbestellung ( R ) + [ n ].
Für den obigen Baum ist das [1, 2, 9, 8, 3, 5, 7, 4, 6] .
Das Durchlaufen eines vollständigen Binärbaums in der Reihenfolge wird rekursiv wie folgt definiert:
- Das Durchlaufen eines Blattes in der Reihenfolge, das einen Knoten n enthält, ist die Liste [ n ].
- Das Durchlaufen einer Verzweigung in der Reihenfolge eines Zweigs , der einen Knoten n und Unterbäume ( L , R) enthält, ist die Liste in der Reihenfolge ( L ) + [ n ] + in der Reihenfolge ( R ).
Für den obigen Baum ist das [1, 3, 2, 8, 9, 6, 5, 4, 7] .
Fazit: Angesichts des Listenpaars [6, 3, 1, 8, 2, 9, 4, 5, 7] (vor) und [1, 2, 9, 8, 3, 5, 7, 4, 6] (post) als Eingabe sollte Ihr Programm [1, 3, 2, 8, 9, 6, 5, 4, 7] ausgeben .
Testfälle
Jeder Testfall hat das Format preorder, postorder → expected output
.
[8], [8] → [8]
[3,4,5], [4,5,3] → [4,3,5]
[1,2,9,8,3], [9,8,2,3,1] → [9,2,8,1,3]
[7,8,10,11,12,2,3,4,5], [11,12,10,2,8,4,5,3,7] → [11,10,12,8,2,7,4,3,5]
[1,2,3,4,5,6,7,8,9], [5,6,4,7,3,8,2,9,1] → [5,4,6,3,7,2,8,1,9]
"CDE" and "DEC" give "DCE"
? (sogar mit Unicode-Buchstaben, wenn ich viele Knoten brauche)"CDE"
es nicht sehr verschieden ist von[67, 68, 69]
:)Antworten:
Perl,
6966625653 BytesBeinhaltet +1 für
-p
Nimmt Nachbestellung gefolgt von Vorbestellung als eine durch Leerzeichen auf STDIN getrennte Zeile an (beachten Sie die Reihenfolge von Vor- und Nachbestellung). Knoten werden als eindeutige Buchstaben dargestellt (jedes Zeichen, das kein Leerzeichen oder keine neue Zeile ist, ist in Ordnung).
inpost.pl
::Die Verwendung des ursprünglichen rein numerischen Formats erfordert viel mehr Sorgfalt bei der genauen Identifizierung einer einzelnen Zahl und liegt bei 73 Byte
Benutzen als
quelle
-p
fügt;
am Ende ein hinzu, sodass Sie das letzte nicht benötigen;
.s;.* ;;
->s;.* ;
;
am Ende. Aber -p fügt tatsächlich\n;
das Ende eines-e
Programms hinzu. In einer Datei wird genau;
dann hinzugefügt, wenn die Datei nicht endet\n
. Da ich-p
+1 und nicht +3 beanspruchen möchte, muss das Programm über die Befehlszeile arbeiten, also mit-e
. Und ich möchte nicht die falsche Newline in der Ausgabe, die ich dann bekommen würde'
es nicht? Wenn Sie es so ausführen, wie Sie es haben (rufen Sie eine Datei mit auf<<<
), können Sie das letzte;
weglassen.'
oder Anwendungendo$0
etc.) I Partitur immer-p
als 3 (Raum, minus, p), aber wenn der Code würde auch funktionieren Auf der Kommandozeile, wo Sie das-e
und das'
kostenlos erhalten, bewerte ich es als,+1
da es mit deme
'
kostenlos bist . Danke, dass du das geklärt hast.Haskell,
8483 Bytesquelle
JavaScript (ES6), 100 Byte
E / A besteht aus Zeichenfolgen mit "sicheren" Zeichen (z. B. Buchstaben oder Ziffern). Alternativer Ansatz, auch 100 Bytes:
quelle