Алгоритмы и структуры данных

Симметричный обход (in-order traversal) двоичного дерева

Симметричный обход дерева (in-order traversal) — это рекурсивный процесс, при котором сначала посещается левая часть поддерева узла, затем сам узел и в завершение — правая часть поддерева:
  1. Посетить левое поддерево (node.left)
  1. Посетить текущий узел
  1. Посетить правое поддерево (node.right)
Можно представить себе, что дерево «подвешено» за корень, а вы читаете его значения слева направо.
Дано двоичное дерево. Необходимо выполнить его симметричный обход (in-order traversal).

Входные данные

Во входных данных находятся целые числа, разделенные пробелами, которые соответствуют значениям в узлах двоичного дерева. Порядок значений задан таким образом, что при «сборке» дерева всегда переходят к левой ветви, а затем к правой. Значение 0 означает отсутствие узла. Гарантируется, что входное двоичное дерево корректно.

Выходные данные

Программа должна вывести значения узлов двоичного дерева при симметричном обходе. Все значения нужно разделить пробелом.

Примеры

Входные данные
Выходные данные
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

Пояснение

  1. Пример 1:
      2. notion image
  1. Пример 2:
      2. notion image
  1. Пример 3:
      2. notion image
  1. Пример 4:
      2. notion image
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue