package shiyan2;

import week8.LinkedBinaryTree;

import java.util.Scanner;


public class ReConstructBinaryTree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入中序序列：");
        String inOrder = scanner.nextLine();   // 中序序列
        System.out.println("请输入先序序列：");
        String preOrder = scanner.nextLine();    //  先序序列

        String[] in = inOrder.split("\\s+");
        String[] pre = preOrder.split("\\s+");

        LinkedBinaryTree tree = ReConstructBinaryTreeCore(in,pre);

        System.out.println("推出的二叉树为");
        System.out.println(tree.toString());

    }

    //核心递归方法
    public static LinkedBinaryTree ReConstructBinaryTreeCore(String[] in, String[] pre)
    {
        LinkedBinaryTree tree;
        if(pre.length == 0 || in.length == 0 || pre.length != in.length){ // 终止递归的条件
            tree =  new LinkedBinaryTree();
        }
        else {
            int x = 0;
            while (!(in[x] .equals( pre[0]))) {   // 找到根结点
                x++;
            }

            String[] inLeft = new String[x];       // 根结点的左边为左子树，创建新的数组
            String[] preLeft = new String[x];
            String[] inRight = new String[in.length - x - 1];       // 根结点的右边为右子树，创建新的数组
            String[] preRight = new String[pre.length - x - 1];

            for (int y = 0; y < in.length; y++) {   // 把原数组的数存入新的数组当中
                if (y < x) {
                    inLeft[y] = in[y];
                    preLeft[y] = pre[y + 1];
                } else if (y > x) {
                    inRight[y - x - 1] = in[y];
                    preRight[y - x - 1] = pre[y];
                }
            }
            LinkedBinaryTree left = ReConstructBinaryTreeCore(inLeft, preLeft);   // 左子树递归调用
            LinkedBinaryTree right = ReConstructBinaryTreeCore(inRight, preRight); // 右子树递归调用
            tree = new LinkedBinaryTree(pre[0], left,right);
        }
        return tree;
    }
}