Pré-encomenda + pós-encomenda para encomenda

11

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 é , 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 :

                                      1

Ou um ramo , consistindo em um 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]
Lynn
fonte
Como a entrada é garantida para ter uma forma específica (uma árvore binária completa), você realmente não precisa das duas entradas, precisa?
feersum 26/09/16
A árvore binária está cheia , mas não completa , portanto, uma árvore com elementos n pode ter muitas formas e, em geral, você precisa das duas.
Lynn
Posso representar os nós como letras únicas, dando seqüências de caracteres para as ordens. Por exemplo, o segundo exemplo se tornaria "CDE" and "DEC" give "DCE":? (mesmo usando letras unicode se eu precisar de lotes de nós)
Ton Hospel
@TonHospel eu estaria bem com isso - sem dúvida, tudo o que você está fazendo é esticar a definição de uma lista de números inteiros um pouco, porque "CDE"não é muito diferente de [67, 68, 69]:)
Lynn

Respostas:

2

Perl, 69 66 62 56 53 bytes

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

inpost.pl:

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

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

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

Use como

inpostnum.pl <<< "11,12,10,2,8,4,5,3,7 7,8,10,11,12,2,3,4,5"
Ton Hospel
fonte
-padiciona um ;no final, para que você não precise do último ;. s;.* ;;->s;.* ;
Riley
@Riley eu sei. É por isso que eu tenho ;o final. Mas -p na verdade adiciona \n;ao final de um -eprograma. Em um arquivo, ele adiciona apenas ;se e somente se o arquivo não terminar \n. Como eu quero reivindicar -pcomo +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
Ton Hospel 26/09/16
Se você executá-lo na linha de comando, não precisa 'contorná-lo? Se você executá-lo da maneira que você o possui (chame um arquivo com <<<), você pode deixar o último ;desligado.
Riley
@Riley Depende da interpretação do método de pontuação para perl. Normalmente, envio meu código como um arquivo, pois acho que é menos efêmero. Mas se você olhar para meus envios, verá que, se o código precisar estar em um arquivo (porque, por exemplo, ele tem 'ou usa do$0etc.), sempre pontuo -pcomo +3 (espaço, menos, p), mas se o código também funcionar na linha de comando onde você recebe o -ee o 'de graça, eu +1o e
pontuo
Ok, eu não estava claro exatamente como a pontuação dos envios de linha de comando. Eu não sabia que você ganha 'de graça. Obrigado por esclarecer isso.
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
fonte
2

JavaScript (ES6), 100 bytes

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]

AE / S está em cadeias de caracteres "seguros" (por exemplo, letras ou dígitos). Abordagem alternativa, também 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
fonte