Обратный обход (post-order traversal) двоичного дерева
Обход дерева в порядке post-order — это рекурсивная процедура, при которой сначала посещается левое поддерево узла, затем его правое поддерево и только после этого сам узел:
- Visit the left subtree (
node.left)
- Visit the right subtree (
node.right)
- Visit the current node
По заданному двоичному дереву требуется выполнить обход в порядке post-order.
Входные данные
Входные данные содержат целые числа, разделённые пробелами, которые соответствуют значениям узлов двоичного дерева. Порядок этих значений задаётся при обходе от левого к правому поддереву. Число 0 означает, что узел отсутствует. Гарантируется, что введённое двоичное дерево является корректным.
Выходные данные
Программа должна вывести значения узлов двоичного дерева при выполнении обхода в порядке post-order, разделяя их одним пробелом.
Примеры
Входные данные | Выходные данные |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 8 9 4 5 2 6 7 3 1 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 8 4 5 2 6 7 3 1 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 4 5 2 6 8 9 7 3 1 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 7 8 5 2 6 3 1 |
Пояснение
- Пример 1:
.png?table=block&id=18a2c681-664d-811a-99e7-f9f3a21c3a32&cache=v2)
- Пример 2:
.png?table=block&id=18a2c681-664d-8153-8ef4-f1be61122330&cache=v2)
- Пример 3:
.png?table=block&id=18a2c681-664d-81b4-aa8f-e39bc521a61e&cache=v2)
- Пример 4:
.png?table=block&id=18a2c681-664d-813c-a8e7-e130d4a1fd60&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB