Tarea

Dados los recorridos de orden previo y posterior de un árbol binario completo, devuelva su recorrido en orden.

Los recorridos se representarán como dos listas, ambas con n enteros positivos distintos, cada uno identificando un nodo de forma única. Su programa puede tomar estas listas y generar el recorrido en orden resultante, utilizando cualquier formato de E / S razonable.

Puede suponer que la entrada es válida (es decir, las listas en realidad representan recorridos de algún árbol).

Este es el código de golf , por lo que gana el código más corto en bytes.

Definiciones

Un árbol binario completo es una estructura finita de nodos , representada aquí por enteros positivos únicos.

Un árbol binario completo es una hoja , que consta de un solo nodo :

                                      1

O una rama , que consiste en un nodo con dos subárboles (llamados los subárboles izquierdo y derecho ), cada uno de los cuales es, a su vez, un árbol binario completo:

                                      1
                                    /   \
                                  …       …

Aquí hay un ejemplo completo de un árbol binario completo:

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

El recorrido de preorden de un árbol binario completo se define de forma recursiva de la siguiente manera:

• El recorrido de preorden de una hoja que contiene un nodo n es la lista [ n ].
• El recorrido de preorden de una rama que contiene un nodo ny subárboles (L, R) es la lista [ n ] +  preordenar ( L ) +  preorder ( R ), donde + es el operador de concatenación de lista.

Para el árbol anterior, eso es [6, 3, 1, 8, 2, 9, 4, 5, 7] .

El recorrido de orden posterior de un árbol binario completo se define de forma recursiva de la siguiente manera:

• El recorrido de orden posterior de una hoja que contiene un nodo n es la lista [ n ].
• El recorrido postorden de una rama que contiene un nodo n y sub-árboles (L, R) es la lista de orden posterior ( L ) +  postorden ( R ) + [ n ].

Para el árbol anterior, eso es [1, 2, 9, 8, 3, 5, 7, 4, 6] .

El recorrido en orden de un árbol binario completo se define de forma recursiva de la siguiente manera:

• El recorrido en orden de una hoja que contiene un nodo n es la lista [ n ].
• El recorrido en orden de una rama que contiene un nodo n y sub-árboles (L, R) es la lista finde ( L ) + [ n ] +  finde ( R ).

Para el árbol anterior, eso es [1, 3, 2, 8, 9, 6, 5, 4, 7] .

En conclusión: dado el par de listas [6, 3, 1, 8, 2, 9, 4, 5, 7] (pre) y [1, 2, 9, 8, 3, 5, 7, 4, 6] (post) como entrada, su programa debería generar [1, 3, 2, 8, 9, 6, 5, 4, 7] .

Casos de prueba

Cada caso de prueba está en el 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]

Perl, 69 66 62 56 53 bytes

Incluye +1 para -p

Toma el postorder seguido de preorder como una línea separada por espacio en STDIN (observe el orden de pre y post). Los nodos se representan como letras únicas (cualquier carácter que no sea espacio o nueva línea está bien).

inpost.pl <<< "98231 12983"

inpost.pl:

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

El uso del formato original puramente numérico necesita mucho más cuidado para identificar exactamente un solo número y viene en 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;.+ ;;

Usar como

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

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

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]

I / O está en cadenas de caracteres "seguros" (por ejemplo, letras o dígitos). Enfoque alternativo, también 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]