Обход бинарного дерева – DEV Community 👩‍💻👨‍💻

mobanto September 7, 2022

Давайте разберем задачу обхода бинарного дерева. Ее можно найти по ссылке
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) Создаем функцию помощник

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) В конце основной функции возвращаем список результатов.

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

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

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)
По памяти – 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)
    }
}

Source link