| Submit | All submissions | Best solutions | Back to list |
EDUPT05 - Pre, Em, Pos |
Um problema comum em estruturas de dados é determinar o percurso de uma árvore binária de busca.
Existem três maneiras clássicas de fazer isso:
Pré-ordem: Você deve visitar em sequência a raiz, a subárvore esquerda e a subárvore direita.
Em ordem: Você deve visitar em sequência a subárvore esquerda, a raiz e a subárvore direita.
Pós-ordem: Você deve visitar em sequência a subárvore esquerda, a subárvore direita e a raiz.
Veja a imagem abaixo:
35
/ \
24 55
/ \
10 67
\
12
Os percursos pré, em e pós-ordem são, respectivamente, . 35;24;10;12;55;67; ----- 10;12;24;35;55;67; ----- 12;10;24;67;55;35;
Neste problema, você deve calcular o percurso pós-ordem de uma árvore binária de busca, considerando seus percursos em ordem e pré-ordem.
Entrada
O conjunto de entrada consiste em um número positivo C ≤ 2000, que fornece o número de casos de teste e linhas C, 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 nesta árvore binária.
Depois, haverá duas sequencias S1 e S2 que descrevem os percursos em pré-ordem e em ordem da árvore.
Os nós da árvore são rotulados com diferentes valores de valor máximo 2000.
Os valores de N, bem como as sequencias S1 e S2, são separados por um espaço em branco.
Dentro de S1 e S2 os valores são seguidos de ';' .
Resultado
Para cada conjunto de entrada, você deve gerar uma linha contendo o percurso em pós-ordem para a árvore atual, com cada valor separado seguido de ';' e com o percurso finalizado com '\n'
Exemplo:
| Entrada | Saída |
|
3 |
10;67;12; 67;55;24; |
| Added by: | IFTM_Maratona |
| Date: | 2022-07-01 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | C |
| Resource: | adaptado de Sebastiao Alves |
RSS