Question

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution

package question105;

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

class Solution {

    private int[] preOrder;
    private int[] inOrder;
    private int idx = 0;
    private Map<Integer, Integer> idxMap = new HashMap<>();


    public static void main(String[] args) {
        int[] preOrder = {3, 9, 20, 15, 7};
        int[] inOrder = {9, 3, 15, 20, 7};

        Solution solution = new Solution();
        solution.buildTree(preOrder, inOrder);
    }


    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        this.preOrder = preOrder;
        this.inOrder = inOrder;

        for (int i = 0; i < inOrder.length; i++) {
            idxMap.put(inOrder[i], i);
        }
        return helper(0, inOrder.length);
    }

    private TreeNode helper(int left, int right) {
        if (left == right) return null;
        TreeNode root = new TreeNode(preOrder[idx]);

        int index = idxMap.get(root.val);
        idx++;
        root.left = helper(left, index);
        root.right = helper(index + 1, right);

        return root;

    }

}

Execution time: 7 milliseconds, defeated in all Java commits 92.51% User
Memory consumption: 36.9 MB , defeated in all Java commits 80.63% User