← Static tasks

105. Construct Binary Tree from Preorder and Inorder Traversal

leetcode medium

#array#csharp#hash-table#leetcode#medium#recursion#tree#two-pointers

Task

Даны два массива целых чисел: 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]

C# solution

matched/original
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;
    }
}

C++ solution

auto-draft, review before submit
#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;
    }
}

Java solution

matched/original
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; }
}

JavaScript solution

matched/original
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);
};

Python solution

matched/original
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)

Go solution

matched/original
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)
}

Explanation

Algorithm

1️⃣

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

2️⃣

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

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

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

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

3️⃣

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

😎