Recorrido in-order (en orden) de un árbol binario
El recorrido in-order de un árbol es un procedimiento recursivo en el que, primero, se visita el subárbol izquierdo de un nodo, luego el nodo mismo y, por último, su subárbol derecho:
- Visitar el subárbol izquierdo (
node.left)
- Visitar el nodo actual
- Visitar el subárbol derecho (
node.right)
Es como si colgáramos el árbol binario desde la raíz y luego leyéramos sus valores de izquierda a derecha.
Dado un árbol binario, se le solicita realizar un recorrido in-order en él.
Entrada
La entrada contiene números enteros separados por espacios que representan los valores en los nodos del árbol binario. El orden de los valores se determina al recorrer siempre desde el subárbol izquierdo hasta el subárbol derecho. Un valor de 0 significa que el nodo no existe. Se garantiza que el árbol binario de entrada es válido.
Salida
El programa debe imprimir los valores en los nodos de un árbol binario al realizar un recorrido in-order. Todos los valores deben aparecer separados por un espacio.
Ejemplos
Entrada | Salida |
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 |
Explicación
- Ejemplo 1:
.png?table=block&id=18a2c681-664d-810a-a345-f487a9a2b024&cache=v2)
- Ejemplo 2:
.png?table=block&id=18a2c681-664d-8106-9e00-fbe2215511fc&cache=v2)
- Ejemplo 3:
.png?table=block&id=18a2c681-664d-8185-bd32-df6ad8b58721&cache=v2)
- Ejemplo 4:
.png?table=block&id=18a2c681-664d-814f-9861-f33b602192c4&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB