Сложность: medium
Даны два массива целых чисел: preorder и inorder, где preorder — это результат преордер обхода бинарного дерева, а inorder — результат инордер обхода того же дерева. Постройте и верните бинарное дерево.
Пример:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
👨💻 Алгоритм:
1️⃣Создайте хеш-таблицу для записи соотношения значений и их индексов в массиве inorder, чтобы можно было быстро найти позицию корня.
2️⃣Инициализируйте переменную целочисленного типа preorderIndex для отслеживания элемента, который будет использоваться для создания корня. Реализуйте рекурсивную функцию arrayToTree, которая принимает диапазон массива inorder и возвращает построенное бинарное дерево: Если диапазон пуст, возвращается null; Инициализируйте корень элементом preorder[preorderIndex], затем увеличьте preorderIndex; Рекурсивно используйте левую и правую части массива inorder для построения левого и правого поддеревьев.
3️⃣Просто вызовите функцию рекурсии с полным диапазоном массива inorder.
😎 Решение:
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def array_to_tree(left, right):
nonlocal preorder_index
if left > right:
return None
root_value = preorder[preorder_index]
root = TreeNode(root_value)
preorder_index += 1
root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
root.right = array_to_tree(inorder_index_map[root_value] + 1, right)
return root
preorder_index = 0
inorder_index_map = {}
for index, value in enumerate(inorder):
inorder_index_map[value] = index
return array_to_tree(0, len(preorder) - 1)
Ставь 👍 и забирай 📚 Базу знаний