public class T006 {

     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};

         preorderTraversalRec(construct(pre,in,8));

     }

     public static void preorderTraversalRec(TreeNode root) {

         if (root == null) {

             return;

         }

         System.out.print(root.val + " ");

         preorderTraversalRec(root.left);

         preorderTraversalRec(root.right);

     }

     public static TreeNode construct(int[] pre,int[] in,int length){

         if(pre == null ||in == null||length<=0)

             return null;

         return constructCore(pre,in,0,length-1,0,length-1);

     }

     public static TreeNode constructCore(int[] pre,int[] in,int startPre,int endPre,int startIn,int endIn){

         int rootValue = pre[startPre];

         TreeNode root = new TreeNode(rootValue);

         root.left = null;

         root.right = null;

         if(startPre == endPre){

             if(startIn == endIn&&startPre==startIn){

                 System.out.println("root");

                 return root;

             }

         }

         int rootIn = startIn;

         while(rootIn<=endIn&&in[rootIn]!=rootValue){

             ++ rootIn;

         }

         if(rootIn == endIn&&in[rootIn]!=rootValue){

             System.out.println("Invalid input2");

         }

         int leftLength = rootIn - startIn;

         int leftPreEnd = startPre + leftLength;

         if(leftLength>0){

             root.left = constructCore(pre,in,startPre+1,leftPreEnd,startIn,rootIn-1);

         }

         if(leftLength<endPre-startPre){

             root.right = constructCore(pre,in,leftPreEnd+1,endPre,rootIn+1,endIn);

         }

         return root;

     }

     private static class TreeNode {

         int val;

         TreeNode left;

         TreeNode right;

         public TreeNode(int val) {

             this.val = val;

         }

     }

 }