package LBT2;

import java.util.Scanner;
import java.util.StringTokenizer;

public class CreateTree {
    public LinkedBinaryTree<String> CreatTree(String inorder[],String preorder[]){
        LinkedBinaryTree<String> binaryTree = null;
        if(inorder.length == preorder.length && inorder.length != 0 && preorder.length != 0){
            int n = 0;

            while (!inorder[n].equals(preorder[0])) {
                n++;
            }

            String[] preLeft = new String[n];
            String[] inLeft = new String[n];

            String[] preRight = new String[preorder.length - n - 1];
            String[] inRight = new String[inorder.length - n - 1];
            for (int t = 0; t < inorder.length; t++) {
                if (t < n) {
                    preLeft[t] = preorder[t + 1];//左子树生成
                    inLeft[t] = inorder[t];//左子树生成
                }
                if (t > n) {
                    preRight[t - n - 1] = preorder[t];//右子树生成
                    inRight[t - n - 1] = inorder[t];//右子树生成
                }
                if(t == n){//
                    continue;
                }
            }

            LinkedBinaryTree<String> left = CreatTree(inLeft, preLeft);
            LinkedBinaryTree<String> right = CreatTree(inRight, preRight);
            binaryTree = new LinkedBinaryTree<String>(preorder[0], left, right);

        }else
        {
            binaryTree = new LinkedBinaryTree(0);
        }
        return binaryTree;
    }

    public static void main(String[] args)
    {
        String a,b;
        int i = 0,j = 0;
        Scanner scanner  = new Scanner(System.in);
        System.out.println("Input the PreOrder：");
        a = scanner.nextLine();
        System.out.println("Input the InOrder：");
        b = scanner.nextLine();

        StringTokenizer str1 = new StringTokenizer(a, " ");
        StringTokenizer  str2= new StringTokenizer(b, " ");

        String[] string1 = new String[str1.countTokens()];
        String[] string2 = new String[str2.countTokens()];

        while (str1.hasMoreTokens())
        {
            string1[i] = str1.nextToken();
            i++;
        }


        while (str2.hasMoreTokens())
        {
            string2[j] = str2.nextToken();
            j++;
        }


        CreateTree ct = new CreateTree();
        LinkedBinaryTree<String> binaryTree = ct.CreatTree(string2,string1);
        System.out.println("The Tree is：");
        System.out.println();
        System.out.println(binaryTree.toString());
    }
}