Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PREEMPOS - Pré, Em e Pós

Um problema comum em estruturas de dados é determinar o percorrimento de uma árvore binária. Existem três maneiras clássicas de fazer isso:

Pré-ordem: Você deve visitar primeiro a raiz, depois a sub-árvore esquerda e por último a sub-árvore direita.
Em-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a raiz e por último a sub-árvore direita.
Pós-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a sub-árvore direita e por último a raiz.

Veja a figura abaixo:

    A
   / \
  B   D
 /   / \
C   E   F

O resultado do percurso em pré, em e pós-ordem é, respectivamente: ABCDEF, CBAEDF e CBEFDA. Neste problema, você deve computar o percurso em pós-ordem de uma árvore binária dados os seus percursos em-ordem e pré-ordem.

Entrada

O conjunto de entrada consiste de um número C ≤ 2000, que dá o número de casos de teste e C linhas, uma para cada caso de teste. Cada caso de teste começa com um número 1 ≤ N ≤ 52, o número de nós nessa árvore arbitrária. Depois, há duas cadeias de caracteres S1 e S2 que descrevem o resultado do percurso da árvore em pré-ordem e em-ordem. Os nós da árvore são rotulados com caracteres diferentes no intervalo a..z e A..Z. Os valores de N, S1 e S2 são separados por um espaço em branco.

Saída

Para cada conjunto de entrada, você deve imprimir uma linha contendo o percorrimento em pós-ordem da árvore correspondente.

Exemplo

Entrada:
3
3 xYz Yxz
3 abc cba
6 ABCDEF CBAEDF

Saída:
Yzx
cba
CBEFDA


Autor do Problema: Sebastião Alves

Adicionado por:Wanderley Guimarăes
Data:2007-10-07
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Segunda Seletiva para Maratona de Programacao UFRN - 2004

hide comments
2011-05-23 12:59:49 [ UERN - UFPB ] Thalles Robson
Sebastiăo Alves foi Meu Professor!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.