Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal
Сложность: medium

Даны два массива целых чисел: inorder и postorder, где inorder — это массив обхода в глубину бинарного дерева слева направо, а postorder — это массив обхода в глубину после обработки всех потомков узла. Постройте и верните соответствующее бинарное дерево.

Пример:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

👨‍💻 Алгоритм:

1⃣Создайте хэш-таблицу (hashmap) для хранения соответствия значений и их индексов в массиве обхода inorder.

2⃣Определите вспомогательную функцию helper, которая принимает границы левой и правой части текущего поддерева в массиве inorder. Эти границы используются для проверки, пусто ли поддерево. Если левая граница больше правой (in_left > in_right), то поддерево пустое и функция возвращает None.

3⃣Выберите последний элемент в массиве обхода postorder в качестве корня. Значение корня имеет индекс index в обходе inorder. Элементы от in_left до index - 1 принадлежат левому поддереву, а элементы от index + 1 до in_right — правому поддереву. Согласно логике обхода postorder, сначала рекурсивно строится правое поддерево helper(index + 1, in_right), а затем левое поддерево helper(in_left, index - 1). Возвращается корень.

😎 Решение:

function buildTree($inorder, $postorder) {
    $idx_map = [];
    $post_idx = count($postorder) - 1;
    $helper = function($in_left, $in_right) use (&$helper, &$postorder, &$idx_map, &$post_idx) {
        if ($in_left > $in_right) return null;
        $root_val = $postorder[$post_idx];
        $root = new TreeNode($root_val);
        $index = $idx_map[$root_val];
        $post_idx--;
        $root->right = $helper($index + 1, $in_right);
        $root->left = $helper($in_left, $index - 1);
        return $root;
    };
    foreach ($inorder as $i => $val) {
        $idx_map[$val] = $i;
    }
    return $helper(0, count($inorder) - 1);
}

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