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

Давайте разберем задачу про вид сбоку бинарного дерева. Ее можно найти по ссылке Binary Tree Right Side View

Постановка задачи

단 코렌 비나르노고 데레바. Представьте, что вы стоите справа от него. Верните значения всех вершин, которые вы видите, отсортированные по порядку сверху-вниз.

Примеры входных данных

프라이머 1

Входные данные:
루트 = [1, 2, 3, 널, 5, 널, 4]
결과:
[1, 3, 4]

예문 2

Входные данные:
루트 = [1, null, 3]
결과:
[1, 3]

프라이머 3

Входные данные:
루트 = []
결과:
[]

레슈니예

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

Решение по шаgamm

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

if (root == null) return emptyList()

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

val result: MutableList<Int> = mutableListOf()

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

val marker: TreeNode = TreeNode(-101)

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

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

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

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

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

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

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

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
}