Обход бинарного дерева
Tags: kotlin, algorithms, leetcode, easy
Published: 2022-09-07 04:33:19

Давайте разберем задачу обхода бинарного дерева. Ее можно найти по ссылке
[Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)

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

## Примеры входных данных
### Пример 1
**Входные данные:**
root = [1, null, 2, 3]
**Результат:**
[1, 3, 2]

### Пример 2
**Входные данные:**
root = []
**Результат:**
[]

### Пример 3
**Входные данные:**
root = [1]
**Результат:**
[1]

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

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

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

```kotlin
val res: MutableList<Int> = mutableListOf()
```

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

```kotlin
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](https://leetcode.com/problems/binary-tree-preorder-traversal/submissions/)

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

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

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

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

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

### Postorder
[Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/submissions/)

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

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

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

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

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

## Оценка сложности алгоритма обхода бинарного дерева
- Временная сложность: O(n). Алгоритм имеет линейную временную сложность, так как каждая вершина дерева посещается ровно один раз в процессе обхода. Здесь n обозначает количество вершин в дереве.
- Сложность по памяти: O(n). Алгоритм обладает линейной сложностью по памяти, поскольку использует рекурсию, и глубина рекурсии может достигать n в самом худшем случае (для вырожденного дерева). Также требуется хранить результирующий список, который содержит n элементов.

## Полное решение
```kotlin
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)
    }
}
```