Tâche

Étant donné les traversées pré et post-ordre d'un arbre binaire complet, retournez sa traversée dans l'ordre.

Les traversées seront représentées sous la forme de deux listes, chacune contenant n entiers positifs distincts, chacun identifiant de manière unique un nœud. Votre programme peut prendre ces listes et produire la traversée dans l'ordre résultante, en utilisant n'importe quel format d'E / S raisonnable.

Vous pouvez supposer que l'entrée est valide (c'est-à-dire que les listes représentent en fait les traversées de certains arbres).

Il s'agit de code-golf , donc le code le plus court en octets l'emporte.

Définitions

Un arbre binaire complet est une structure finie de nœuds , représentée ici par des entiers positifs uniques.

Un arbre binaire complet est soit une feuille , constituée d'un seul nœud :

                                      1

Ou une branche , constituée d'un nœud avec deux sous-arbres (appelés sous-arbres gauche et droit ), chacun étant à son tour un arbre binaire complet:

                                      1
                                    /   \
                                  …       …

Voici un exemple complet d'arbre binaire complet:

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

La traversée en précommande d'un arbre binaire complet est définie de manière récursive comme suit:

• La traversée en pré-commande d'une feuille contenant un nœud n est la liste [ n ].
• La traversée en pré-commande d'une branche contenant un nœud n et des sous-arbres (L, R) est la liste [ n ] +  pré-commande ( L ) +  pré-commande ( R ), où + est l'opérateur de concaténation de liste.

Pour l'arbre ci-dessus, c'est [6, 3, 1, 8, 2, 9, 4, 5, 7] .

La traversée post-commande d'un arbre binaire complet est définie de manière récursive comme suit:

• La traversée post-commande d'une feuille contenant un nœud n est la liste [ n ].
• Le parcours postfixe d'une branche contenant un noeud n et des sous-arbres (L, R) est la liste postorder ( L ) +  postorder ( R ) + [ n ].

Pour l'arbre ci-dessus, c'est [1, 2, 9, 8, 3, 5, 7, 4, 6] .

La traversée dans l'ordre d'un arbre binaire complet est définie de manière récursive comme suit:

• La traversée dans l'ordre d'une feuille contenant un nœud n est la liste [ n ].
• La traversée dans l'ordre d'une branche contenant un nœud n et des sous-arbres (L, R) est la liste inorder ( L ) + [ n ] +  inorder ( R ).

Pour l'arbre ci-dessus, c'est [1, 3, 2, 8, 9, 6, 5, 4, 7] .

En conclusion: étant donné la paire de listes [6, 3, 1, 8, 2, 9, 4, 5, 7] (pré) et [1, 2, 9, 8, 3, 5, 7, 4, 6] (post) en entrée, votre programme devrait sortir [1, 3, 2, 8, 9, 6, 5, 4, 7] .

Cas de test

Chaque scénario de test est au 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]

Perl, 69 66 62 56 53 octets

Comprend +1 pour -p

Prend la post-commande suivie de la précommande comme une ligne séparée par un espace sur STDIN (notez l'ordre de pré-publication et de post-publication). Les nœuds sont représentés comme des lettres uniques (tout caractère qui n'est ni espace ni nouvelle ligne est OK).

inpost.pl <<< "98231 12983"

inpost.pl:

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

L'utilisation du format purement numérique d'origine nécessite beaucoup plus de soin pour identifier exactement un seul numéro et se présente à 73 octets

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

Utilisé comme

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

Haskell, 84 83 octets

(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 octets

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]

Les E / S sont des chaînes de caractères "sûrs" (par exemple des lettres ou des chiffres). Approche alternative, également 100 octets:

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]