Tarefa
Dadas as travessias de pré e pós-ordem de uma árvore binária completa, retorne sua travessia em ordem.
As travessias serão representadas como duas listas, ambas contendo n números inteiros positivos distintos, cada um identificando exclusivamente um nó. Seu programa pode pegar essas listas e produzir a passagem em ordem resultante, usando qualquer formato de E / S razoável.
Você pode assumir que a entrada é válida (ou seja, as listas realmente representam travessias de alguma árvore).
Isso é código-golfe , então o código mais curto em bytes vence.
Definições
Uma árvore binária completa é uma estrutura finita de nós , representada aqui por números inteiros positivos exclusivos.
Uma árvore binária completa é uma folha , consistindo em um único nó :
1
Ou um ramo , consistindo em um nó com duas subárvores (chamadas subárvores esquerda e direita ), cada uma das quais é, por sua vez, uma árvore binária completa:
1 / \ … …
Aqui está um exemplo completo de uma árvore binária completa:
6
/ \
3 4
/ \ / \
1 8 5 7
/ \
2 9
O percurso de pré-ordem de uma árvore binária completa é definido recursivamente da seguinte maneira:
- A travessia de pré-ordem de uma folha contendo um nó n é a lista [ n ].
- O percurso de pré-ordem de um ramo contendo um nó n e subárvores (L, R) é a lista [ n ] + pré-encomenda ( L ) + pré-encomenda ( R ), onde + é o operador de concatenação da lista.
Para a árvore acima, isso é [6, 3, 1, 8, 2, 9, 4, 5, 7] .
A travessia pós-ordem de uma árvore binária completa é definida recursivamente da seguinte maneira:
- A travessia pós-ordem de uma folha contendo um nó n é a lista [ n ].
- A travessia pós-ordem de um ramo contendo um nó n e subárvores (L, R) é a lista de ordem posterior ( L ) + ordem posterior ( R ) + [ n ].
Para a árvore acima, isso é [1, 2, 9, 8, 3, 5, 7, 4, 6] .
A travessia em ordem de uma árvore binária completa é definida recursivamente da seguinte maneira:
- O percurso em ordem de uma folha contendo um nó n é a lista [ n ].
- A travessia em ordem de uma ramificação contendo um nó n e subárvores (L, R) é a lista na ordem ( L ) + [ n ] + na ordem ( R ).
Para a árvore acima, isso é [1, 3, 2, 8, 9, 6, 5, 4, 7] .
Em conclusão: dado o par de listas [6, 3, 1, 8, 2, 9, 4, 5, 7] (pré) e [1, 2, 9, 8, 3, 5, 7, 4, 6] (post) como entrada, seu programa deve gerar [1, 3, 2, 8, 9, 6, 5, 4, 7] .
Casos de teste
Cada caso de teste está no formato 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"
:? (mesmo usando letras unicode se eu precisar de lotes de nós)"CDE"
não é muito diferente de[67, 68, 69]
:)Respostas:
Perl,
6966625653 bytesInclui +1 para
-p
Faz a encomenda posterior seguida da encomenda como uma linha separada por espaço no STDIN (observe a ordem de pré e pós). Os nós são representados como letras exclusivas (qualquer caractere que não seja espaço ou nova linha está OK).
inpost.pl
:O uso do formato puramente numérico original precisa de muito mais cuidado para identificar exatamente um único número e aparece com 73 bytes
Use como
fonte
-p
adiciona um;
no final, para que você não precise do último;
.s;.* ;;
->s;.* ;
;
o final. Mas -p na verdade adiciona\n;
ao final de um-e
programa. Em um arquivo, ele adiciona apenas;
se e somente se o arquivo não terminar\n
. Como eu quero reivindicar-p
como +1 e não +3, o programa precisa trabalhar a partir da linha de comando-e
. E eu não quero a nova linha espúria na saída que eu teria então'
contorná-lo? Se você executá-lo da maneira que você o possui (chame um arquivo com<<<
), você pode deixar o último;
desligado.'
ou usado$0
etc.), sempre pontuo-p
como +3 (espaço, menos, p), mas se o código também funcionar na linha de comando onde você recebe o-e
e o'
de graça, eu+1
oe
'
de graça. Obrigado por esclarecer isso.Haskell,
8483 bytesfonte
JavaScript (ES6), 100 bytes
AE / S está em cadeias de caracteres "seguros" (por exemplo, letras ou dígitos). Abordagem alternativa, também 100 bytes:
fonte