java实现给定前序和后序遍历的二叉树重建

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

　　例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
分析：中序遍历：左孩子--当前元素--后孩子
前序遍历：当前元素--左孩子--后孩子
由此可得：前序遍历中“1”为第一个元素，说明其是根，就可以在中序里面找，“1”在第四位

如上图一样，那么我们就可以知道{4,7,2}为左字数，{5,3,8,6}为右子树，所以我们又可以将前序里的{2,4,7}和中序里的{4,7,2}重新做一次上面的操作，这里使用递归的方法：

public static void main(String[] args) {
       int[] pre= {1,2,4,7,3,5,6,8};//前序遍历数组
       int[] in= {4,7,2,1,5,3,8,6};//中序遍历数组
      tree root= fun(pre,in,0,pre.length-1,0,in.length-1);//调用fun方法

       prePrint(root);//前序遍历树以验证正确
    }
    public static tree fun(int[] pre,int[] in,int preleft,int preright,int inleft,int inright){
if(preleft>preright||inleft>inright)
    return null;
tree node=new tree(pre[preleft]);
for(int i=inleft;i<=inright;i++)
{
    if(in[i]==pre[preleft])
    {
        node.left=fun(pre,in,preleft+1,preleft+i-inleft,inleft,i-1);
        node.right=fun(pre,in,preleft+i+1-inleft,preright,1+i,inright);
        break;
    }
}
return node;
    }
//前序遍历方法
    public static void prePrint(tree root){

        System.out.println(root.val);
        if(root.left!=null)
        {prePrint(root.left);}
        if(root.right!=null)
        {prePrint(root.right);}

    }