Задача: 105. Construct Binary Tree from Preorder and Inorder Traversal
Сложность: 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.

😎 Решение:

function buildTree($preorder, $inorder) {
    static $preorderIndex = 0;
    $inorderIndexMap = [];
    foreach ($inorder as $i => $value) {
        $inorderIndexMap[$value] = $i;
    }
    
    return arrayToTree(0, count($preorder) - 1, $preorder, $inorderIndexMap, $preorderIndex);
}

function arrayToTree($left, $right, &$preorder, &$inorderIndexMap, &$preorderIndex) {
    if ($left > $right) {
        return null;
    }
    
    $rootValue = $preorder[$preorderIndex++];
    $root = new TreeNode($rootValue);
    $root->left = arrayToTree($left, $inorderIndexMap[$rootValue] - 1, $preorder, $inorderIndexMap, $preorderIndex);
    $root->right = arrayToTree($inorderIndexMap[$rootValue] + 1, $right, $preorder, $inorderIndexMap, $preorderIndex);
    return $root;
}

class TreeNode {
    public $val;
    public $left;
    public $right;

    public function __construct($value) {
        $this->val = $value;
        $this->left = null;
        $this->right = null;
    }
}

Ставь 👍 и забирай 📚 Базу знаний