Populating Next Right Pointers in Each Node II

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

У каждого узла двоичного дерева есть ещё один указатель, next, сначала он none. Нужно направить next каждого узла на соседа справа на том же уровне; у самого правого узла уровня остаётся none. Дерево не обязательно полное, на уровне бывают пропуски. Вернуть корень. Наш пример: дерево [6, 2, 9, 1, 4, none, 8] по уровням — после прогона уровни читаются так: 6 → none; 2 → 9 → none; 1 → 4 → 8 → none.

117 Populating Next Right Pointers in Each Node IIРазбор · 1×

Пример: связать каждый узел [6, 2, 9, 1, 4, none, 8] с соседом справа на его уровне.

629148очередьначало слева—
не достигнутждёт в очередитекущийготов

Дерево не пустое

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

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

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

  1. Очередь хранит узлы по уровням: потомки встают в конец, за всеми ещё не взятыми узлами уровня.
  2. Поэтому пока i < size, в начале очереди — следующий узел того же уровня, от какого бы родителя он ни был.
  3. Последний узел уровня (i = size) видит впереди уже следующий уровень, поэтому его next остаётся none.

Сложность

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

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

Решить на LeetCode ↗

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