Прямой обход (pre-order) бинарного дерева
Прямой обход дерева — это рекурсивная процедура, при которой сначала посещается текущий узел, затем обходится левое поддерево, а после этого — правое поддерево:
Посетить текущий узел
Перейти в левое поддерево (
node.left)Перейти в правое поддерево (
node.right)
Для заданного бинарного дерева требуется выполнить прямой (pre-order) обход.
Входные данные
Во входных данных содержатся целые числа, разделённые пробелами, которые представляют значения в узлах бинарного дерева. Порядок значений задан так, как описано в предыдущем разделе (при каждом обходе сначала идёт левое поддерево, а потом правое). Значение 0 означает отсутствие узла. Гарантируется, что входное бинарное дерево корректно.
Выходные данные
Программа должна вывести значения в узлах бинарного дерева при прямом (pre-order) обходе. Все значения требуется отделять одним пробелом.
Примеры
Входные данные | Выходные данные |
|---|---|
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 |
Пояснение
Пример 1:
Пример 2:
Пример 3:
Пример 4:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB