Back to DSA

Construct Binary Tree from Preorder and Inorder Traversal

medium
Acceptance: 54%
Binary Tree

Two integer arrays representing the pre-order and in-order traversals of a binary tree are given. Both arrays contain the same set of unique values. Reconstruct the original binary tree and return its root.

Examples

Example 1:
Input:preorder = [1,2,4,5,3,6], inorder = [4,2,5,1,6,3]
Output:[1,2,3,4,5,6,null]

Hints

Related Problems

Maximum Depth of Binary TreeeasyInvert Binary TreeeasyValidate Binary Search TreemediumLowest Common Ancestor of a Binary TreemediumBinary Tree Level Order Traversalmedium
00:00
import java.util.*;

class Solution {
    private int preIdx = 0;
    private Map<Integer, Integer> inMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int left, int right) {
        if (left > right) return null;
        int rootVal = preorder[preIdx++];
        TreeNode root = new TreeNode(rootVal);
        int mid = inMap.get(rootVal);
        root.left = build(preorder, left, mid - 1);
        root.right = build(preorder, mid + 1, right);
        return root;
    }
}
Time complexityO(n)
Space complexityO(n)