Zadanie

Biorąc pod uwagę przechodzenie przed i po zamówieniu pełnego drzewa binarnego, zwróć przechodzenie w kolejności.

Przejścia będą reprezentowane jako dwie listy, obie zawierające n odrębnych liczb całkowitych dodatnich, z których każda jednoznacznie identyfikuje węzeł. Twój program może pobrać te listy i wygenerować wynikowe przechodzenie w kolejności przy użyciu dowolnego rozsądnego formatu we / wy.

Możesz założyć, że dane wejściowe są prawidłowe (to znaczy, że listy faktycznie reprezentują przechodzenie przez niektóre drzewa).

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.

Definicje

Pełne drzewo binarne jest skończona budowa węzłów , reprezentowany tutaj przez unikalnych liczb całkowitych dodatnich.

Pełne drzewo binarne jest albo liściem składającym się z jednego węzła :

                                      1

Lub gałąź , składająca się z jednego węzła z dwoma poddrzewami (zwanymi poddrzewami lewym i prawym ), z których każde jest z kolei pełnym drzewem binarnym:

                                      1
                                    /   \
                                  …       …

Oto pełny przykład pełnego drzewa binarnego:

                                        6
                                      /   \
                                    3       4
                                   / \     / \
                                  1   8   5   7
                                     / \
                                    2   9

Przejścia pre-order z pełnego drzewa binarnego jest rekurencyjnie zdefiniowane następująco:

• Przejście w przód liścia zawierającego węzeł n to lista [ n ].
• Przejście do góry gałęzi zawierającej węzeł n i poddrzewa (L, R) to lista [ n ] +  zamówienie wstępne ( L ) +  zamówienie wstępne ( R ), gdzie + jest operatorem konkatenacji listy.

Dla powyższego drzewa jest to [6, 3, 1, 8, 2, 9, 4, 5, 7] .

Przejścia post-order z pełnego drzewa binarnego jest rekurencyjnie zdefiniowane następująco:

• Przejście po zamówieniu liścia zawierającego węzeł n to lista [ n ].
• Przejście po zamówieniu gałęzi zawierającej węzeł ni poddrzewa (L, R) to lista postorder ( L ) +  postorder ( R ) + [ n ].

Dla powyższego drzewa jest to [1, 2, 9, 8, 3, 5, 7, 4, 6] .

Przejścia na zamówienie pełnego drzewa binarnego jest rekurencyjnie zdefiniowane następująco:

• Kolejność przechodzenia przez liść zawierający węzeł n to lista [ n ].
• Kolejność przechodzenia gałęzi zawierającej węzeł n i poddrzewa (L, R) to lista inorder ( L ) + [ n ] +  inorder ( R ).

Dla powyższego drzewa jest to [1, 3, 2, 8, 9, 6, 5, 4, 7] .

Podsumowując: biorąc pod uwagę parę list [6, 3, 1, 8, 2, 9, 4, 5, 7] (pre) i [1, 2, 9, 8, 3, 5, 7, 4, 6] (post) jako dane wejściowe, twój program powinien wypisać [1, 3, 2, 8, 9, 6, 5, 4, 7] .

Przypadki testowe

Każdy przypadek testowy ma 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]

Perl, 69 66 62 56 53 bajtów

Obejmuje +1 dla -p

Przyjmuje postorder, a następnie preorder jako jeden wiersz oddzielony spacją na STDIN (zwróć uwagę na kolejność pre i post). Węzły są reprezentowane jako unikalne litery (dowolny znak, który nie jest spacją lub znakiem nowej linii, jest OK).

inpost.pl <<< "98231 12983"

inpost.pl:

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

Używanie oryginalnego formatu czysto numerycznego wymaga dużo więcej uwagi, aby dokładnie zidentyfikować pojedynczy numer i ma 73 bajty

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

Użyj jako

inpostnum.pl <<< "11,12,10,2,8,4,5,3,7 7,8,10,11,12,2,3,4,5"

Haskell, 84 83 bajtów

(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

JavaScript (ES6), 100 bajtów

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]

We / wy składa się z ciągów „bezpiecznych” znaków (np. Liter lub cyfr). Alternatywne podejście, również 100 bajtów:

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]