Percurso em pré-ordem de uma árvore binária
O percurso em pré-ordem de uma árvore é um procedimento recursivo no qual primeiro se visita um nó, depois a sua subárvore esquerda e, por fim, a sua subárvore direita:
- Visitar o nó atual
- Visitar a subárvore esquerda (
node.left)
- Visitar a subárvore direita (
node.right)
Dada uma árvore binária, pede-se que realizes um percurso em pré-ordem sobre ela.
Entrada
A entrada contém inteiros separados por espaço que representam os valores dos nós da árvore binária. A ordem dos valores é fornecida conforme a descrição anterior (percorrendo sempre da subárvore esquerda para a subárvore direita). Um valor de 0 significa que o nó não existe. Garante-se que a árvore binária de entrada é válida.
Saída
O programa deve imprimir os valores dos nós de uma árvore binária ao realizar um percurso em pré-ordem. Todos os valores devem ser 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 | 1 2 4 8 9 5 3 6 7 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 1 2 4 8 5 3 6 7 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 1 2 4 5 3 6 7 8 9 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 1 2 4 5 7 8 3 6 |
Explicação
- Exemplo 1:
.png?table=block&id=18a2c681-664d-81e5-a7e5-d3b75f833c71&cache=v2)
- Exemplo 2:
.png?table=block&id=18a2c681-664d-81e4-9ff6-d047acfceb81&cache=v2)
- Exemplo 3:
.png?table=block&id=18a2c681-664d-81e5-a9f4-e449ba85ffed&cache=v2)
- Exemplo 4:
.png?table=block&id=18a2c681-664d-8174-84fa-ff579ec09088&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB