Binary Tree Postorder Traversal

Лёгкая№145обратный

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

145 Binary Tree Postorder TraversalРазбор · 1×

Пример: обратный обход двоичного дерева с одним своим стеком вместо рекурсии. У каждого узла есть val, left и right.

nonenonenonenonenonenone49258out—стеквершина справа—
ещё не дошлив стекеcur или node на вершине стекав out, #n — его местоnone: пустой потомок

out = []: пока ничего не посетили

01/66
сначала · назад · пуск · шаг
Скорость
1function postorderTraversal(root):
2 out = []
3 stack = []
4 cur = root
5 last = none
6 while cur is not none or stack is not empty:
7 if cur is not none:
8 stack.push(cur)
9 cur = cur.left
10 else:
11 node = stack.top()
12 if node.right is not none and node.right is not last:
13 cur = node.right
14 else:
15 out.add(node.val)
16 last = stack.pop()
17 return out
состояние
cur
–
node
–
last
–
stack
–
out
[]
историянажмите шаг, чтобы вернуться

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

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

  1. В стеке лежит путь от корня до cur, как вызовы в рекурсивном обходе. Узел уходит из него, только когда оба его поддерева уже в out.
  2. Узел с правым потомком оказывается на вершине стека дважды: до своего правого поддерева и после него. last — узел, который только что попал в out, поэтому если node.right — это last, мы возвращаемся.
  3. Без last во второй раз мы снова ушли бы вправо и зациклились.

Сложность

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

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

Решить на LeetCode ↗

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