Задача: 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). Возвращается корень.

😎 Решение:

var buildTree = function (inorder, postorder) {
    var idx_map = {};
    var post_idx = postorder.length - 1;
    var helper = function (in_left, in_right) {
        if (in_left > in_right) return null;
        var root_val = postorder[post_idx];
        var root = new TreeNode(root_val);
        var index = idx_map[root_val];
        post_idx--;
        root.right = helper(index + 1, in_right);
        root.left = helper(in_left, index - 1);
        return root;
    };
    for (var i = 0; i < inorder.length; i++) idx_map[inorder[i]] = i;
    return helper(0, inorder.length - 1);
};

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