Условие

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

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

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

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

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

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

Примеры

Ввод: 7 3 2 1 9 5 4 6 8 0 Вывод: 2 9

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

// Класс узла бинарного дерева поиска (BST)
class Node(val value: Int) {
    var left: Node? = null
    var right: Node? = null
}

// Класс бинарного дерева поиска (BST)
class BST {
    var root: Node? = null // Корневой узел дерева

    // Метод вставки нового элемента в дерево
    fun insert(value: Int) {
        root = insertRec(root, value)
    }

    // Рекурсивный метод вставки значения в дерево
    private fun insertRec(node: Node?, value: Int): Node {
        if (node == null) return Node(value) // Создаем новый узел, если достигли пустого места
        when {
            value < node.value -> node.left = insertRec(node.left, value) // Вставляем в левое поддерево
            value > node.value -> node.right = insertRec(node.right, value) // Вставляем в правое поддерево
        }
        return node
    }

    // Метод для вывода всех узлов, у которых только один потомок
    fun printOneChildNodes(writer: BufferedWriter) {
        collectOneChildNodes(root, writer)
    }

    // Рекурсивный метод поиска узлов с одним потомком
    private fun collectOneChildNodes(node: Node?, writer: BufferedWriter) {
        if (node == null) return
        collectOneChildNodes(node.left, writer) // Обходим левое поддерево
        if ((node.left == null) xor (node.right == null)) { // Если у узла только один потомок
            writer.write("${node.value}\\n")
        }
        collectOneChildNodes(node.right, writer) // Обходим правое поддерево
    }
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val bst = BST() // Создаем экземпляр бинарного дерева поиска
    val parts = reader.readLine().split(" ").map { it.toInt() } // Читаем входные данные

    // Вставляем числа в дерево, прерываемся при встрече 0
    for (num in parts) {
        if (num == 0) break
        bst.insert(num)
    }

    bst.printOneChildNodes(writer) // Выводим узлы, у которых только один потомок

    reader.close()
    writer.flush()
    writer.close()
}