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]
"CDE" and "DEC" give "DCE"
? (nawet używając liter Unicode, jeśli potrzebuję wielu węzłów)"CDE"
nie różni się zbytnio od[67, 68, 69]
:)Odpowiedzi:
Perl,
6966625653 bajtówObejmuje +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
:Używanie oryginalnego formatu czysto numerycznego wymaga dużo więcej uwagi, aby dokładnie zidentyfikować pojedynczy numer i ma 73 bajty
Użyj jako
źródło
-p
dodaje;
na końcu, więc nie potrzebujesz ostatniego;
.s;.* ;;
->s;.* ;
;
na końcu. Ale -p faktycznie dodaje\n;
się do końca w-e
programie. W pliku dodaje się tylko;
wtedy i tylko wtedy, gdy plik się nie kończy\n
. Ponieważ chcę żądać-p
jako +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'
go w pobliżu? Jeśli uruchomisz go tak, jak go masz (zadzwoń do pliku za pomocą<<<
), możesz zostawić ostatni;
wyłączony.'
lub używado$0
itp.), Zawsze oceniam-p
jako +3 (spacja, minus, p), ale jeśli kod również by działał w wierszu polecenia, w którym dostajesz,-e
i'
za darmo+1
e
'
za darmo. Dzięki za wyjaśnienie.Haskell,
8483 bajtówźródło
JavaScript (ES6), 100 bajtów
We / wy składa się z ciągów „bezpiecznych” znaków (np. Liter lub cyfr). Alternatywne podejście, również 100 bajtów:
źródło