Давайте разберем задачу обхода бинарного дерева. Ее можно найти по ссылке
Неупорядоченный обход двоичного дерева


Постановка задач

Дана корневая врешина бинарного дерева. Вернуть список всех вершин «по очереди».


Примеры входных данных


Пример 1

Входные данные:
корень = [1, null, 2, 3]Результат:
[1, 3, 2]


Пример 2

Входные данные:
корень = []Результат:
[]


Пример 3

Входные данные:
корень = [1]Результат:
[1]


Отвечать

При обходе дерева «по очереди» необходимо сначала посетить левую дочернюю вершину дерева, затем — текущую, а после этого — правую дочернюю вершину.


Решение по шагам

1) Заводим результирующий список

val res: MutableList<Int> = mutableListOf()
Войти в полноэкранный режим

Выйти из полноэкранного режима

2) Создаем функцию помощник

private fun helper(node: TreeNode?, res: MutableList<Int>) {
    if (node != null) {
        helper(node.left, res)
        res.add(node.`val`)
        helper(node.right, res)
    }
}
Войти в полноэкранный режим

Выйти из полноэкранного режима

В функцию помощник необходимо передавать текущую вершину дерева и список результатов.

3) В функции сначала проверяем на null текущую вершину. Мы делаем рекурсивный вызов функции, а это является терминирующим условием.

4) Далее рекурсивно вызываем функцию helper на левой дочерней вершине.

5) Затем добавляем значение текущей вершины в список результатов.

6) А потом рекурсвивно вызываем функцию helper на правой дочерней вершине.

7) В конце основной функции возвращаем список результатов.


Вариации задачи

Рассмотрим так же две вариации этой задачи.


Предварительный заказ

Обход предварительного заказа двоичного дерева

Первая вариация, когда мы добавляем значение вершины в список ответов до обхода дочерних вершин. Изменяются только шаги 4-6.

res.add(node.`val`)
helper(node.left, res)
helper(node.right, res)
Войти в полноэкранный режим

Выйти из полноэкранного режима

4) Добавляем значение текущей вершины в список результатов.

5) Рекурсвивно вызываем функцию helper на левой дочерней вершине.

6) Рекурсвивно вызываем функцию helper на правой дочерней вершине.


Заказ по почте

Обход двоичного дерева в обратном порядке

Во второй вариации необходимо добавлять значение вершины в ответ после посещения дочерних вершин. Так же изменяются только шаги 4-6.

helper(node.left, res)
helper(node.right, res)
res.add(node.`val`)
Войти в полноэкранный режим

Выйти из полноэкранного режима

4) Рекурсвивно вызываем функцию helper на левой дочерней вершине

5) Рекурсвивно вызываем функцию helper на правой дочерней вершине

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


Оценка сложности

  • По времени — O(n)
  • По памяти — O(n)


Полное решение

fun inorderTraversal(root: TreeNode?): List<Int> {
    val res: MutableList<Int> = mutableListOf()
    helper(root, res)
    return res
}

private fun helper(node: TreeNode?, res: MutableList<Int>) {
    if (node != null) {
        helper(node.left, res)
        res.add(node.`val`)
        helper(node.right, res)
    }
}
Войти в полноэкранный режим

Выйти из полноэкранного режима