Вид сбоку бинарного дерева
Tags: kotlin, algorithms, leetcode, medium
Published: 2022-09-11 06:32:44

Давайте разберем задачу про вид сбоку бинарного дерева. Ее можно найти по ссылке [Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)

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

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

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

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

## Решение
Задача, которую необходимо решить, связана с обходом графа в ширину. Обход графа в ширину - это алгоритм, который позволяет посетить все вершины графа, начиная с заданной вершины, просматривая сначала все вершины, находящиеся на расстоянии 1 от данной вершины, затем все вершины, находящиеся на расстоянии 2 и т.д.

Для выполнения задачи необходимо реализовать алгоритм обхода графа в ширину с дополнительной функциональностью. При обходе графа необходимо отслеживать уровень дерева, на котором мы находимся. Для этого можно использовать очередь, в которую будут добавляться все вершины, находящиеся на расстоянии k от начальной вершины. Также необходимо вести отдельный счетчик для уровня дерева.

После того, как все вершины на текущем уровне были посещены, необходимо добавить в результирующий массив последний элемент данного уровня. Для этого можно использовать дополнительный указатель на последний посещенный элемент. После перехода на следующий уровень дерева данный указатель будет указывать на последний элемент текущего уровня, который затем будет добавлен в результирующий массив.

Таким образом, реализация алгоритма обхода графа в ширину с отслеживанием уровня дерева позволит решить данную задачу.

## Решение по шагам
**1)** Для начала надо проверить, не является ли входная вершина значению null

```kotlin
if (root == null) return emptyList()
```

**2)** Затем необходимо инициализировать результирующий список

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

**3)** Далее создаем маркерную вершину для разделения уровней

```kotlin
val marker: TreeNode = TreeNode(-101)
```

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

```kotlin
val queue: ArrayDeque<TreeNode> = ArrayDeque()
queue.addLast(root)
queue.addLast(marker)
```

**5)** В цикле по очереди достаем элемент с начала очереди

```kotlin
while(queue.size > 1) {
	val node = queue.removeFirst()
}
```

**6)** Если этот элемент является маркером, то записываем в ответ предыдущую вершину

```kotlin
if (node == marker) {
    result.add(prevNode.`val`)
    queue.addLast(marker)
}
```

**7)** Если этот элемент не является маркером, то сохраняем временно предуыдущую вершину. А затем добавляем в очередь дочерние элементы.

```kotlin
prevNode = node
node.left?.also { queue.addLast(it) }
node.right?.also { queue.addLast(it) }
```

**8)** После выхода из цикла добавляем в ответ последний временно сохраненный результат.

```kotlin
result.add(prevNode.`val`)
```

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

```kotlin
fun rightSideView(root: TreeNode?): List<Int> {
    if (root == null) return emptyList()
    val result: MutableList<Int> = mutableListOf()
    val marker: TreeNode = TreeNode(-101)
    val queue: ArrayDeque<TreeNode> = ArrayDeque()
    queue.addLast(root)
    queue.addLast(marker)
    var prevNode: TreeNode = marker
    while(queue.size > 1) {
        val node = queue.removeFirst()
        if (node == marker) {
            result.add(prevNode.`val`)
            queue.addLast(marker)
        } else {
            prevNode = node
            node.left?.also { queue.addLast(it) }
            node.right?.also { queue.addLast(it) }
        }
    }
    result.add(prevNode.`val`)
    return result
}
```