Construct Binary Tree from Preorder and Inorder Traversal

Средняя№105построить дерево

Даны два обхода одного двоичного дерева с разными значениями: прямой (узел, левое поддерево, правое) и симметричный (левое поддерево, узел, правое). Нужно восстановить дерево. Наши обходы: прямой [1, 7, 3, 4, 5, 6], симметричный [3, 7, 4, 1, 5, 6] — дерево по уровням: [1, 7, 5, 3, 4, none, 6].

105 Construct Binary Tree from Preorder and Inorder TraversalРазбор · 1×

Пример: восстановить двоичное дерево по прямому обходу [1, 7, 3, 4, 5, 6] и симметричному [3, 7, 4, 1, 5, 6].

011723344556031724314556preorderinorder
ещё не использованодиапазон текущего вызова в симметричном обходеval: текущий узелждёт поддеревоиспользовано, поддерево готово

pos = {3: 0, 7: 1, 4: 2, 1: 3, 5: 4, 6: 5}: где стоит каждое значение в симметричном обходе, за O(1)

01/55
сначала · назад · пуск · шаг
Скорость
1function buildTree(preorder, inorder):
2 pos = map from each value to its index in inorder
3 next = 0 // index of the next root in preorder
4 return build(0, len(inorder) - 1)
5
6function build(lo, hi):
7 if lo > hi:
8 return none
9 val = preorder[next]
10 next = next + 1
11 mid = pos[val]
12 node = new node(val)
13 node.left = build(lo, mid - 1)
14 node.right = build(mid + 1, hi)
15 return node
состояние
next
–
lo
–
hi
–
val
–
mid
–
нажмите шаг, чтобы вернуться

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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