126. Вывод веток

Для бинарного дерева поиска, построенного на заданных элементах, выведите список всех вершин, имеющих только одного ребёнка, в порядке возрастания.

Бинарным деревом поиска называется двоичное дерево, для которого выполняются следующие свойства:

• Оба поддерева — левое и правое — являются двоичными деревьями поиска.

• У всех узлов левого поддерева произвольного узла X значения ключей данных строго меньше, нежели значение ключа данных самого узла X.

• У всех узлов правого поддерева произвольного узла X значения ключей данных строго больше, нежели значение ключа данных самого узла X.

Обратите внимание, что при таком определении, в дереве не могут встречаться узлы с одинаковым значением ключей. Если во входных данных несколько раз встречается какое-то число, то в построенном бинарном дереве оно будет присутствовать в единственном экземпляре.

Вводится последовательность целых чисел, оканчивающаяся нулем. Построить по ней дерево.

Выведите список требуемых вершин.