Binary Tree Preorder Traversal

Лёгкая№144прямой

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

144 Binary Tree Preorder TraversalРазбор · 1×

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

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

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

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

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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