Список узлов, видимых с правой стороны бинарного дерева

Условие

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

Пример дерева:

      3
     / \
    1   4
   / \   \
  0   2   5

Ответ: (3, 4, 5)

Ответ

Обойдите дерево по уровням и возьмите последний узел каждого уровня. При добавлении левого ребёнка раньше правого это и будет вид справа.

from collections import deque

def right_view(root):
    if root is None:
        return []
    queue = deque([root])
    result = []
    while queue:
        level_size = len(queue)
        for index in range(level_size):
            node = queue.popleft()
            if index == level_size - 1:
                result.append(node.val)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
    return result

Предполагаются поля val, left и right. Для дерева из условия результат [3, 4, 5]. Важен последний узел всего уровня, а не просто цепочка правых детей: на глубоком уровне видимым может оказаться узел левого поддерева. Время O(n), память O(w), где w — максимальная ширина дерева.