105. Construct Binary Tree from Preorder and Inorder Traversal

public class Solution {
    private int preorderIndex;
    private Dictionary<int, int> inorderIndexMap;
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        preorderIndex = 0;
        inorderIndexMap = new Dictionary<int, int>();
        for (int i = 0; i < inorder.Length; i++) {
            inorderIndexMap[inorder[i]] = i;
        }
        return ArrayToTree(preorder, 0, preorder.Length - 1);
    }
    private TreeNode ArrayToTree(int[] preorder, int left, int right) {
        if (left > right)
            return null;
        int rootValue = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootValue);
        root.left = ArrayToTree(preorder, left, inorderIndexMap[rootValue] - 1);
        root.right =
            ArrayToTree(preorder, inorderIndexMap[rootValue] + 1, right);
        return root;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int preorderIndex;
    private unordered_map<int, int> inorderIndexMap;
    public TreeNode BuildTree(vector<int>& preorder, vector<int>& inorder) {
        preorderIndex = 0;
        inorderIndexMap = new unordered_map<int, int>();
        for (int i = 0; i < inorder.size(); i++) {
            inorderIndexMap[inorder[i]] = i;
        }
        return ArrayToTree(preorder, 0, preorder.size() - 1);
    }
    private TreeNode ArrayToTree(vector<int>& preorder, int left, int right) {
        if (left > right)
            return null;
        int rootValue = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootValue);
        root.left = ArrayToTree(preorder, left, inorderIndexMap[rootValue] - 1);
        root.right =
            ArrayToTree(preorder, inorderIndexMap[rootValue] + 1, right);
        return root;
    }
}

class Solution {
    int preorderIndex;
    Map<Integer, Integer> inorderIndexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preorderIndex = 0;
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        return arrayToTree(preorder, 0, preorder.length - 1);
    }

    private TreeNode arrayToTree(int[] preorder, int left, int right) {
        if (left > right) return null;
        int rootValue = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootValue);
        root.left = arrayToTree(
            preorder,
            left,
            inorderIndexMap.get(rootValue) - 1
        );
        root.right = arrayToTree(
            preorder,
            inorderIndexMap.get(rootValue) + 1,
            right
        );
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) { val = x; }
}

var buildTree = function (preorder, inorder) {
    let preorderIndex = 0;
    let inorderIndexMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderIndexMap.set(inorder[i], i);
    }
    function arrayToTree(left, right) {
        if (left > right) return null;
        let rootValue = preorder[preorderIndex++];
        let root = new TreeNode(rootValue);
        root.left = arrayToTree(left, inorderIndexMap.get(rootValue) - 1);
        root.right = arrayToTree(inorderIndexMap.get(rootValue) + 1, right);
        return root;
    }
    return arrayToTree(0, preorder.length - 1);
};

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)

func buildTree(preorder []int, inorder []int) *TreeNode {
    preorderIndex := 0
    inorderIndexMap := make(map[int]int)
    for i := 0; i < len(inorder); i++ {
        inorderIndexMap[inorder[i]] = i
    }
    var arrayToTree func(left int, right int) *TreeNode
    arrayToTree = func(left int, right int) *TreeNode {
        if left > right {
            return nil
        }
        rootValue := preorder[preorderIndex]
        preorderIndex++
        root := &TreeNode{Val: rootValue}
        root.Left = arrayToTree(left, inorderIndexMap[rootValue]-1)
        root.Right = arrayToTree(inorderIndexMap[rootValue]+1, right)
        return root
    }
    return arrayToTree(0, len(preorder)-1)
}

Algorithm

1️⃣

Создайте хеш-таблицу для записи соотношения значений и их индексов в массиве inorder, чтобы можно было быстро найти позицию корня.

2️⃣

Инициализируйте переменную целочисленного типа preorderIndex для отслеживания элемента, который будет использоваться для создания корня. Реализуйте рекурсивную функцию arrayToTree, которая принимает диапазон массива inorder и возвращает построенное бинарное дерево:

Если диапазон пуст, возвращается null;

Инициализируйте корень элементом preorder[preorderIndex], затем увеличьте preorderIndex;

Рекурсивно используйте левую и правую части массива inorder для построения левого и правого поддеревьев.

3️⃣

Просто вызовите функцию рекурсии с полным диапазоном массива inorder.

😎