Вид сбоку бинарного дерева

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

if (root == null) return emptyList()

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

val result: MutableList<Int> = mutableListOf()

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

val marker: TreeNode = TreeNode(-101)

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

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

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

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

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

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

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

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

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

result.add(prevNode.`val`)

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

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
}