Given the preorder and inorder traversal sequence of a binary tree, reconstruct the original tree.

Assumptions

• The given sequences are not null and they have the same length
• There are no duplicate keys in the binary tree

Examples

preorder traversal = {5, 3, 1, 4, 8, 11}

inorder traversal = {1, 3, 4, 5, 8, 11}

the corresponding binary tree is

    5

  /    \

3        8

/ \

1 4 11

Solution: pre[]第一个为root，找到该数值在in[]的位置（利用hashmap），划分为左半部和右半部

  public TreeNode reconstruct(int[] in, int[] pre) {
    if (in.length == 0) {
      return null;
    }
    Map<Integer, Integer> hashmap = new HashMap<>();
    for (int i = 0; i < in.length; i++) {
      hashmap.put(in[i], i);
    }
    return build(in, 0, in.length - 1, pre, 0, pre.length - 1, hashmap);
  }
  private TreeNode build(int[] in, int instart, int inend, int[] pre, int prestart, int preend, Map<Integer, Integer> hashmap) {
    if (instart > inend) {
      return null;
    }
    TreeNode root = new TreeNode(pre[prestart]);
    // int position = find(inorder, instart, inend, post[postend]);
    int position = hashmap.get(pre[prestart]);
    root.left = build(in, instart, position - 1, pre, prestart + 1, prestart + position - instart, hashmap);
    root.right = build(in, position + 1, inend, pre, prestart + position - instart + 1, preend, hashmap);
    return root;
  }