Construct Binary Tree from Inorder and Postorder Traversal

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

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

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

Пример: восстановить двоичное дерево по симметричному обходу [9, 8, 4, 7, 2, 5] и обратному [8, 9, 7, 5, 2, 4].

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

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

01/56
сначала · назад · пуск · шаг
Скорость
1function buildTree(inorder, postorder):
2 pos = map from each value to its index in inorder
3 next = len(postorder) - 1 // roots from the end
4 return build(0, len(inorder) - 1)
5
6function build(lo, hi):
7 if lo > hi:
8 return none
9 val = postorder[next]
10 next = next - 1
11 mid = pos[val]
12 node = new node(val)
13 node.right = build(mid + 1, hi) // right first
14 node.left = build(lo, mid - 1)
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.