DEV Community 👩‍💻👨‍💻

Ivan
Ivan

Posted on

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

Давайте разберем задачу обхода бинарного дерева. Ее можно найти по ссылке
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()
Enter fullscreen mode Exit fullscreen mode

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

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

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

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)
Enter fullscreen mode Exit fullscreen mode

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

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

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

Postorder

Binary Tree Postorder Traversal

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

helper(node.left, res)
helper(node.right, res)
res.add(node.`val`)
Enter fullscreen mode Exit fullscreen mode

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)
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Find what you were looking for? Sign up so you can:

🌚 Enable dark mode
🔠 Change your default font
📚 Adjust your experience level to see more relevant content