DEV Community

Ivan
Ivan

Posted on • Edited on

16 11 2 1 2

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

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

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

val result: MutableList<Int> = mutableListOf()
Enter fullscreen mode Exit fullscreen mode

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

val marker: TreeNode = TreeNode(-101)
Enter fullscreen mode Exit fullscreen mode

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

val queue: ArrayDeque<TreeNode> = ArrayDeque()
queue.addLast(root)
queue.addLast(marker)
Enter fullscreen mode Exit fullscreen mode

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

while(queue.size > 1) {
    val node = queue.removeFirst()
}
Enter fullscreen mode Exit fullscreen mode

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

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

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

prevNode = node
node.left?.also { queue.addLast(it) }
node.right?.also { queue.addLast(it) }
Enter fullscreen mode Exit fullscreen mode

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

result.add(prevNode.`val`)
Enter fullscreen mode Exit fullscreen mode

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

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

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (1)

Collapse
 
irchiiik profile image
Ирина Лютина

Отлично ))

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay