Flatten Binary Tree to Linked List

Средняя№114прямой

Дан корень двоичного дерева. Нужно на месте превратить его в список по правым ссылкам: все левые ссылки — none, а если идти от корня по right, узлы идут в прямом порядке. Наше дерево: 4 с потомками 8 и 2; у 8 потомки 1 и 6; у 2 левый потомок 5 — ответ 4 → 8 → 1 → 6 → 2 → 5.

114 Flatten Binary Tree to Linked ListРазбор · 1×

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

482165по rightот корня42
ещё не дошлиnode и ссылка, которую только что поменялиlast: последний узел левого поддеревауже в списке

node = root, 4

01/38
сначала · назад · пуск · шаг
Скорость
1function flatten(root):
2 node = root
3 while node is not none:
4 if node.left is not none:
5 last = node.left
6 while last.right is not none:
7 last = last.right
8 last.right = node.right
9 node.right = node.left
10 node.left = none
11 node = node.right
12 return
состояние
node
–
last
–
историянажмите шаг, чтобы вернуться

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

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

  1. В прямом порядке правое поддерево узла идёт сразу за последним узлом его левого поддерева. Этот узел находим, если от node.left идти вправо, пока есть правый потомок.
  2. Если повесить туда правое поддерево, а левое перенести направо, прямой порядок сохраняется, а у node не остаётся левой ссылки.
  3. Потом node шагает вправо, и так обрабатываем каждый узел; всё выше node уже стало одним списком.

Сложность

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

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

Решить на LeetCode ↗

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