Binary Tree Right Side View

Средняя№199узлы дерева

Дан корень двоичного дерева, возможно none. Представь, что стоишь справа от дерева: выпиши значения, которые видно, сверху вниз. На каждом уровне видно только самый правый узел. Наш пример — дерево [6, 2, 9, 5, 4, none, 11, none, none, 8] по уровням — ответ [6, 9, 11, 8].

199 Binary Tree Right Side ViewРазбор · 1×

Пример: выписать, что видно справа у дерева, правый край которого кончается на уровень раньше.

62954118очередьначало слева—
не достигнутв очереди, этот уровеньв очереди, следующий уровеньтекущийпройден

Корень — 6, не none

01/58
сначала · назад · пуск · шаг
Скорость
1function rightSideView(root):
2 if root is none:
3 return []
4 result = []
5 queue = [root]
6 while queue is not empty:
7 size = queue.size
8 for i from 1 to size:
9 node = queue.popFront()
10 if i == size:
11 result.add(node.val)
12 if node.left is not none:
13 queue.pushBack(node.left)
14 if node.right is not none:
15 queue.pushBack(node.right)
16 return result
состояние
result
–
queue
–
size
–
i
–
node
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. BFS проходит уровень слева направо, а size говорит, сколько в нём узлов, поэтому i == size отмечает его самый правый узел.
  2. Справа видно самый правый узел каждого уровня, в каком бы поддереве он ни висел: если идти только по правым потомкам, 8 потеряется.
  3. Каждый уровень даёт ровно одно значение, по порядку сверху, поэтому список и есть вид справа.

Сложность

Время O(n): каждый узел один раз попадает в очередь и один раз из неё выходит. Память O(w): в очереди не больше примерно двух уровней, w — самый широкий.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.