Обход бинарного дерева

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

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

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

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

Пример 1

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

Пример 2

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

Пример 3

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

Решение

Во время обхода бинарного дерева "по очереди" (симметричного), алгоритм следует определенной последовательности посещения вершин: сначала выполняется рекурсивный обход левого поддерева, начиная с его корневой вершины; далее посещается текущая (корневая) вершина; и, наконец, выполняется рекурсивный обход правого поддерева, начиная с его корневой вершины. Таким образом, симметричный обход гарантирует последовательное посещение элементов дерева в соответствии с их сортированным порядком.

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

1) Инициализируем результирующий список, который будет хранить вершины дерева в порядке их обхода

val res: MutableList<Int> = mutableListOf()

2) Создаем вспомогательную рекурсивную функцию helper, которая принимает текущую вершину дерева и список результатов

private fun helper(node: TreeNode?, res: MutableList<Int>) {
    if (node != null) {
        helper(node.left, res)
        res.add(node.`val`)
        helper(node.right, res)
    }
}

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

4) Затем рекурсивно вызываем функцию helper на левой дочерней вершине текущей вершины, что позволяет пройти все левые поддеревья.

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

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

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

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

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

Preorder

Binary Tree Preorder Traversal

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

res.add(node.`val`)
helper(node.left, res)
helper(node.right, res)

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

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

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

Postorder

Binary Tree Postorder Traversal

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

helper(node.left, res)
helper(node.right, res)
res.add(node.`val`)

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

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

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

Оценка сложности алгоритма обхода бинарного дерева

• Временная сложность: O(n). Алгоритм имеет линейную временную сложность, так как каждая вершина дерева посещается ровно один раз в процессе обхода. Здесь n обозначает количество вершин в дереве.
• Сложность по памяти: O(n). Алгоритм обладает линейной сложностью по памяти, поскольку использует рекурсию, и глубина рекурсии может достигать n в самом худшем случае (для вырожденного дерева). Также требуется хранить результирующий список, который содержит 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)
    }
}