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:
.png?table=block&id=18a2c681-664d-81bf-ad2d-e6b70549abb3&cache=v2)
- Exemplo 2:
.png?table=block&id=18a2c681-664d-81bd-94ec-f72aab971fe5&cache=v2)
- Exemplo 3:
.png?table=block&id=18a2c681-664d-81f7-ac65-d047913c40b4&cache=v2)
- Exemplo 4:
.png?table=block&id=18a2c681-664d-8111-83dc-fa4fd02ddded&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB