Zamówienie w przedsprzedaży + zamówienie w porządku

11

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 , 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]
Lynn
źródło
Ponieważ wejście ma zagwarantowany określony kształt (pełne drzewo binarne), tak naprawdę nie potrzebujesz obu danych wejściowych, prawda?
feersum
Drzewo binarne jest pełne , ale nie kompletne , więc drzewo n- elementowe może mieć wiele kształtów i ogólnie potrzebujesz obu.
Lynn
Niech mogę reprezentować węzły jako pojedyncze litery podające ciągi znaków dla zamówień. Np drugim przykładem może stać się: "CDE" and "DEC" give "DCE"? (nawet używając liter Unicode, jeśli potrzebuję wielu węzłów)
Ton Hospel,
@TonHospel Nie miałbym nic przeciwko - prawdopodobnie wszystko, co robisz, to trochę rozszerza definicję listy liczb całkowitych , ponieważ "CDE"nie różni się zbytnio od [67, 68, 69]:)
Lynn

Odpowiedzi:

2

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"
Ton Hospel
źródło
-pdodaje ;na końcu, więc nie potrzebujesz ostatniego ;. s;.* ;;->s;.* ;
Riley
@Riley Wiem. Dlatego mam ;na końcu. Ale -p faktycznie dodaje \n;się do końca w -eprogramie. W pliku dodaje się tylko ;wtedy i tylko wtedy, gdy plik się nie kończy \n. Ponieważ chcę żądać -pjako +1, a nie +3, program musi działać z wiersza polecenia, więc z -e. I nie chcę fałszywej nowej linii na wyjściu, którą wtedy otrzymałbym
Ton Hospel
Jeśli uruchomisz go w wierszu poleceń, czy nie potrzebujesz 'go w pobliżu? Jeśli uruchomisz go tak, jak go masz (zadzwoń do pliku za pomocą <<<), możesz zostawić ostatni ;wyłączony.
Riley,
@Riley Zależy to od interpretacji metody punktacji dla perla. Zwykle przesyłam swój kod jako plik, ponieważ uważam, że jest to mniej efemeryczne. Ale jeśli spojrzysz na moje zgłoszenia, zobaczysz, że jeśli kod musi znajdować się w pliku (ponieważ np. Ma 'lub używa do$0itp.), Zawsze oceniam -pjako +3 (spacja, minus, p), ale jeśli kod również by działał w wierszu polecenia, w którym dostajesz, -ei 'za darmo +1e
oceniam
Okej, po prostu nie byłem do końca pewien, jak dokładnie oceniają wyniki linii poleceń. Nie zdawałem sobie sprawy, że dostajesz 'za darmo. Dzięki za wyjaśnienie.
Riley
3

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
Dianne
źródło
2

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]
Neil
źródło