95. Construct Binary Tree from Preorder and Inorder Traversal

The first value of preorder is always the root. Find that root inside inorder: everything to its left is the left subtree, everything to its right is the right subtree. Recurse, consuming preorder values in order.

Idea

Preorder visits root first, so preorder[0] is the root. In inorder, the root splits the array: values before it form the left subtree, values after form the right. Recurse on those ranges, advancing a shared pointer through preorder (which lists roots top-down, left before right).

A hash map from value → inorder index makes the split O(1).

Algorithm

1. Map each inorder value to its index.
2. Keep a preorder pointer p = 0. build(lo, hi) over an inorder range:
   • If lo > hi, return null.
   • root_val = preorder[p]; p += 1. Find mid = index[root_val].
   • root.left = build(lo, mid-1); root.right = build(mid+1, hi).

Worked example: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

• Root 3; inorder splits into [9] (left) and [15,20,7] (right). Recursing rebuilds [3,9,20,null,null,15,7].

Complexity

• Time: O(n) with the index map.
• Space: O(n).

import java.util.HashMap;
import java.util.Map;

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

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

    private TreeNode build(int[] preorder, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        int rootVal = preorder[pre++];
        TreeNode root = new TreeNode(rootVal);
        int mid = idx.get(rootVal);
        root.left = build(preorder, lo, mid - 1);
        root.right = build(preorder, mid + 1, hi);
        return root;
    }
}