输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
前序：根>左>右 中序： 左>根>右
思路：根据前序遍历可知第一个节点为根节点，在中序中找到该节点位置，其左边所有节点都为根节点的左子树，右边的为右子树，然后使用递归的方法，每次返回其左右子树，直到只剩一个节点时返回该节点的根节点即可。
代码如下：

package tee;
 class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}
public class Test {
	public static void main(String []args){
		int[] pre=new int[]{1,2,4,7,3,5,6,8};
		int[] in=new int[]{4,7,2,1,5,3,8,6};
		Test t=new Test();
		t.reConstructBinaryTree(pre,in);
	}
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        int index=0;
        int []pre1;//左子树的前序和中序遍历
        int []in1;
        int []pre2;//右子树的前序和中序遍历
        int []in2;
        if( pre.length==1){//为1直接返回该节点
                 TreeNode tree1=new TreeNode( pre[0]   );
                return tree1;
        }
        for(int i=0;i<pre.length;i++)//找到根节点在中序中的位置
        {
            if(pre[0]==in[i])
            {
                index=i; 
                break;
            }
        }
        TreeNode tree=new TreeNode(pre[0]);
        //判断是否有左子树
          if(index>0)
        { 
           pre1=new int[index];
            in1=new int[index]; 
            for(int i=0;i<index;i++)
        {
            pre1[i]=pre[i+1];
        }
           for(int i=0;i<index;i++)
        {
            in1[i]=in[i];
        }
         tree.left=reConstructBinaryTree(pre1,in1) ;  //递归      
        }
          //判断是否有右子树
         if(pre.length-index>1)
        {
            int a=pre.length-index-1;
            pre2=new int[a];
            in2=new int[a]; 
           for(int i=index+1;i<pre.length;i++)
        {
            pre2[i-index-1]=pre[i];
        }
           for(int i=index+1;i<pre.length;i++)
        {
            in2[i-index-1]=in[i];
        }
         tree.right=reConstructBinaryTree(pre2,in2); //递归      
        }     
           return tree;
}
}