Percurso in-order (em ordem) numa árvore binária
O percurso in-order de uma árvore é um procedimento recursivo, em que primeiro se visita a subárvore esquerda de um nó, depois o próprio nó e, por fim, a subárvore direita:
Visitar a subárvore esquerda (
node.left)Visitar o nó atual
Visitar a subárvore direita (
node.right)
É como se pendurássemos a árvore binária pela raiz e lêssemos os valores da esquerda para a direita.
Dada uma árvore binária, pretende-se realizar o percurso in-order sobre ela.
Entrada
A input contém inteiros separados por espaços, representando os valores dos nós da árvore binária. A ordem dos valores segue sempre o percurso da subárvore esquerda antes da subárvore direita. Um valor 0 significa que o nó não existe. Garante-se que a árvore binária dada é válida.
Saída
O programa deve imprimir os valores dos nós da árvore binária ao realizar o percurso in-order, separados por um espaço.
Exemplos
Entrada | Saída |
|---|---|
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 8 4 9 2 5 1 6 3 7 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 8 4 2 5 1 6 3 7 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 4 2 5 1 6 3 8 7 9 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 2 7 5 8 1 3 6 |
Explicação
Exemplo 1:
Exemplo 2:
Exemplo 3:
Exemplo 4:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB