Binary Tree Inorder Traversal

Лёгкая№94симметричный

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

94 Binary Tree Inorder TraversalРазбор · 1×

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

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

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

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

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

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

  1. Узел попадает в стек по пути вниз и выходит из него, только когда всё левее него пройдено: стек ждёт так же, как вызовы в рекурсивном обходе.
  2. После того как узел добавлен, cur уходит в его правое поддерево, поэтому порядок всегда такой: левое поддерево, узел, правое поддерево.
  3. Каждый узел кладём в стек и достаём из него один раз, поэтому цикл кончается, когда cur — none и никто не ждёт.

Сложность

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

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

Решить на LeetCode ↗

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