Vorbestellung + Nachbestellung bis In-Order

11

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 , 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]
Lynn
quelle
Da die Eingabe garantiert eine bestimmte Form hat (ein vollständiger Binärbaum), benötigen Sie nicht wirklich beide Eingaben, oder?
Feersum
Der Binärbaum ist voll , aber nicht vollständig , sodass ein n- Element-Baum viele Formen haben kann, und im Allgemeinen benötigen Sie beide.
Lynn
Darf ich die Knoten als einzelne Buchstaben darstellen, die Zeichenfolgen für die Bestellungen geben. ZB würde das zweite Beispiel werden : "CDE" and "DEC" give "DCE"? (sogar mit Unicode-Buchstaben, wenn ich viele Knoten brauche)
Ton Hospel
@ TonHospel Ich wäre damit einverstanden - wohl alles, was Sie tun, ist die Definition einer Liste von ganzen Zahlen ein wenig zu erweitern, weil "CDE"es nicht sehr verschieden ist von [67, 68, 69]:)
Lynn

Antworten:

2

Perl, 69 66 62 56 53 Bytes

Beinhaltet +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 <<< "98231 12983"

inpost.pl::

#!/usr/bin/perl -p
s%(.)(.)+\K(.)(.+)\3(\1.*)\2%$4$5$3$2%&&redo;s;.+ ;;

Die Verwendung des ursprünglichen rein numerischen Formats erfordert viel mehr Sorgfalt bei der genauen Identifizierung einer einzelnen Zahl und liegt bei 73 Byte

#!/usr/bin/perl -p
s%\b(\d+)(,\d+)+\K,(\d+\b)(.+)\b\3,(\1\b.*)\2\b%$4$5,$3$2%&&redo;s;.+ ;;

Benutzen als

inpostnum.pl <<< "11,12,10,2,8,4,5,3,7 7,8,10,11,12,2,3,4,5"
Ton Hospel
quelle
-pfügt ;am Ende ein hinzu, sodass Sie das letzte nicht benötigen ;. s;.* ;;->s;.* ;
Riley
@ Riley Ich weiß. Deshalb habe ich das ;am Ende. Aber -p fügt tatsächlich \n;das Ende eines -eProgramms 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
Ton Hospel
Wenn Sie es über die Befehlszeile ausführen, brauchen Sie 'es nicht? Wenn Sie es so ausführen, wie Sie es haben (rufen Sie eine Datei mit auf <<<), können Sie das letzte ;weglassen.
Riley
@ Riley Es hängt von der Interpretation der Bewertungsmethode für Perl ab. Normalerweise reiche ich meinen Code als Datei ein, da ich denke, dass dies weniger kurzlebig ist. Aber wenn man sich meine Eingaben anschauen , werden Sie sehen , dass , wenn der Code muss in einer Datei sein (zB weil er hat 'oder Anwendungen do$0etc.) I Partitur immer -pals 3 (Raum, minus, p), aber wenn der Code würde auch funktionieren Auf der Kommandozeile, wo Sie das -eund das 'kostenlos erhalten, bewerte ich es als, +1da es mit deme
Ton Hospel
Okay, ich war mir einfach nicht sicher, wie genau die Befehlszeilenübermittlungen abschneiden. Ich wusste nicht, dass du 'kostenlos bist . Danke, dass du das geklärt hast.
Riley
3

Haskell, 84 83 Bytes

(a:b:c)#z|i<-1+length(fst$span(/=b)z),h<- \f->f i(b:c)#f i z=h take++a:h drop
a#_=a
Dianne
quelle
2

JavaScript (ES6), 100 Byte

f=(s,t,l=t.search(s[1]))=>s[1]?f(s.slice(1,++l+1),t.slice(0,l))+s[0]+f(s.slice(l+1),t.slice(l)):s[0]

E / A besteht aus Zeichenfolgen mit "sicheren" Zeichen (z. B. Buchstaben oder Ziffern). Alternativer Ansatz, auch 100 Bytes:

f=(s,t,a=0,b=0,c=s.length-1,l=t.search(s[a+1])-b)=>c?f(s,t,a+1,b,l)+s[a]+f(s,t,l+2+a,l+1,c-l-2):s[a]
Neil
quelle