/**

* public class TreeNode {

* public int key;

* public TreeNode left;

* public TreeNode right;

* public TreeNode(int key) {

* this.key = key;

* }

* }

*/

public class Solution {
  public TreeNode reconstruct(int[] in, int[] level) {
    // Write your solution here.



    if (in == null || level == null || in.length == 0 || level.length == 0 || in.length != level.length) {

      return null;

    }

    // use map to store in order<value,index>; pair to fast locate root position

    //assumption no duplicated number in the sequence

    Map<Integer,Integer> map = new HashMap<Integer,Integer>();

    for(int i = 0; i < in.length; i++) {

      map.put(in[i],i);

    }



    return helper(in, 0, in.length - 1, level, map);
  }

  private TreeNode helper(int[] inorder, int inleft, int inright, int[] level, Map<Integer,Integer> map) {

  //base case

    if (inleft > inright) {

      return null;

    }



    TreeNode root = new TreeNode(level[0]);

    int index = map.get(root.key);

    int size = index - inleft;



    // in the level order sequence, index &lt; index of root will be left subtree, other wise will be right subtree

    int[] leftsub = new int[size];

    int[] rightsub = new int[inright - index];

    int lindex = 0;

    int rindex = 0;



    for (int i = 1; i < level.length; i++) {

      if (map.get(level[i]) < index ) {

        leftsub[lindex++] = level[i];

      } else {

        rightsub[rindex++] = level[i];

      }

    }



    root.left = helper(inorder, inleft, inleft + size - 1, leftsub,map);

    root.right = helper(inorder, inleft + size + 1, inright, rightsub,map);

    return root;
    }

   }