Деревья

Двоичное дерево поиска (BST) — это бинарное дерево, в котором каждый узел имеет значение, и дерево организовано так, что для любого узла все значения в его левом поддереве меньше значения узла, а все значения в его правом поддереве больше значения узла.

Для построения BST из последовательности различных целых чисел используется следующий метод. Первое целое число становится корнем дерева. Затем рассматривается второе число в последовательности. Если оно меньше значения корневого узла, то оно становится левым потомком. В противном случае оно становится правым потомком. Последующие элементы в последовательности перемещаются вниз либо влево, либо вправо таким же образом, в зависимости от сравнения с предыдущими узлами, начиная с корня и продвигаясь вниз по дереву. Новый узел вставляется (как лист) в частично построенное дерево, когда он достигает отсутствующего поддерева в конкретном направлении движения.

Например, BST, сгенерированное последовательностью [2, 1, 4, 3], строится следующим образом по мере вставки чисел.

Рисунок 1: Генерация BST

Дерево (d) на Рисунке 1 также может быть сгенерировано двумя другими последовательностями: [2, 4, 3, 1] и [2, 4, 1, 3].

Такие последовательности можно сравнивать в лексикографическом порядке, где сравнение происходит слева направо, и элементы на соответствующих позициях сравниваются по их числовым значениям. Результат для [2, 1, 4, 3], [2, 4, 3, 1] и [2, 4, 1, 3] следующий, используя "<" для обозначения этого лексикографического порядка между последовательностями: [2, 1, 4, 3] < [2, 4, 1, 3] < [2, 4, 3, 1].

Для дерева (d) на Рисунке 1 лексикографически наименьшая последовательность — это [2, 1, 4, 3].

Напишите программу, которая будет читать представление дерева и генерировать лексикографически наименьшую последовательность различных положительных целых чисел, которая сгенерирует это дерево. Обратите внимание, что для дерева с n узлами эта последовательность будет перестановкой чисел от 1 до n.

Для ввода нашей задачи мы представляем (рекурсивно) структуру дерева следующим образом:

1. Один узел (лист) является деревом:

   • ()

2. Если TL и TR являются деревьями, то следующие также являются деревьями:

   • (TL,)

   • (,TR)

   • (TL,TR)

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

Ввод будет состоять из последовательности строк. Каждая строка будет состоять из не более чем 250 символов и будет содержать спецификацию одного дерева в соответствии с вышеуказанным определением (без промежуточных пробелов). Последовательность будет завершена деревом, состоящим из одного узла (). Эта строка не должна обрабатываться.

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

Вывод будет представлять собой последовательность строк, по одной для каждой строки на входе. Каждая строка будет состоять из требуемой перестановки чисел от 1 до n (где n — количество узлов в дереве), разделенных одиночными пробелами.

Примеры