剑指Offer第四题：重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解答：
递归方法：
public class Q_4 {

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    if (pre.length == 0) {
        return null;
    } else {
        int val = pre[0];
        TreeNode thisnode = new TreeNode(val);
        int[] be = getBefore(in, val);
        int besize = be.length;
        if (besize > 0) {
            int[] bepre = new int[besize];
            for (int m = 0; m < besize; m++) {
                bepre[m] = pre[m + 1];
            }
            TreeNode left = reConstructBinaryTree(bepre, be);//注意找出下一个递归的参数
            thisnode.left = left;
        }

        int[] af = getAfter(in, val);
        int afsize = af.length;
        if (afsize > 0) {
            int[] afpre = new int[afsize];
            for (int m = 0; m < afsize; m++) {
                afpre[m] = pre[m + besize+1];//复制右子树的数据，所以要去除左子树besize个数
            }
            TreeNode right = reConstructBinaryTree(afpre, af);
            thisnode.right = right;
        }

        return thisnode;
    }

}
//下面两个方法可以用Arrays.copyOfRange替代
public int[] getBefore(int[] arr, int val) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    int i = 0;
    while (arr[i] != val) {
        arrayList.add(arr[i]);
        i++;
    }
    int[] beforeArr = new int[arrayList.size()];
    for (int j = 0; j < arrayList.size(); j++) {
        beforeArr[j] = arrayList.get(j);
    }
    return beforeArr;
}

public int[] getAfter(int[] arr, int val) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    boolean start=false;
    for (int i = 0; i < arr.length; i++) {
        if(start){
            arrayList.add(arr[i]);
        }
        if(arr[i]==val) start=true;
    }
    int[] afterArr = new int[arrayList.size()];
    for (int j = 0; j < arrayList.size(); j++) {
        afterArr[j] = arrayList.get(j);
    }
    return afterArr;
}

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};
    TreeNode node=new Q_4().reConstructBinaryTree(pre,in);
    System.out.println(node);
}

}