1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {

    private int[] preorder;
    private int[] inorder;
    private Map<Integer, Integer> inIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;

        for (int i = 0; i < inorder.length; i++) {
            inIndex.put(inorder[i], i);
        }

        return build(0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int preL, int preR, int inL, int inR) {
        if (preL > preR) {
            return null;
        }

        int rootVal = preorder[preL];
        TreeNode root = new TreeNode(rootVal);

        int k = inIndex.get(root.val);
        int leftSize = k - inL;

        root.left = build(preL + 1, preL + leftSize, inL, k + 1);
        root.right = build(preL + leftSize + 1, preR, k + 1, inR);
        return root;
    }
}