import java.util.*;

 /**

  * Definition for binary tree

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode(int x) { val = x; }

  * }

  */

 import java.util.Arrays;

 public class Solution {

     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

         if(pre.length == 0 || in.length == 0){

             return null;

         }

         //前序:{1,2,4,7,3,5,6,8} 中序:{4,7,2,1,5,3,8,6}

         TreeNode node = new TreeNode(pre[0]);

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

             if(pre[0] == in[i]){

                 //注意边界问题

                 //如i=3时，in[i]==pre[0],则中序{4,7,2,1,5,3,8,6}分为左边{4,7,2}和右边{5,3,8,6}。所以left的前序数组只需拷贝从[1,i+1)即可。

                 node.left = this.reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));

                 node.right = this.reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));

             }

         }

         return node;

     }

 }

 copyOfRange(int[] original, int from, int to)

 import java.util.*;

 /**

  * Definition for binary tree

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode(int x) { val = x; }

  * }

  */

 import java.util.Arrays;

 public class Solution {

     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

         TreeNode node = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);

         return node;

     }

     //重载

     private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn){

         //判断数组是否为空

         if(startPre > endPre || startIn > endIn){

             return null;

         }

         TreeNode node = new TreeNode(pre[startPre]);

         for(int i = startIn; i <= endIn; i++){

             if(pre[startPre] == in[i]){

                  //注意边界

                  node.left = reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);

                  node.right = reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);

                  break;

             }

         }

         return node;

     }

 }