用先序和中序遍历重建二叉树

1. 分析
前序遍历：根→左→右
中序遍历：左→根→右

由前序遍历序列pre={1,2,4,7,3,5,6,8}可知根结点是1；
则在中序遍历序列in={4,7,2,1,5,3,8,6}中找到1，便可知1所在位置的左侧是左子树,1所在位置的右侧是右子树；
递归调用：将左子树和右子树分别看成一颗树，将其前序遍历序列、中序遍历序列分别传入到该方法中，便可得到左子树的根结点、右子树的根结点。
此时需要用第一步得到的根结点连接它们；
递归调用的终止条件：直到传入数组为空，说明已经没有节点，直接返回null。

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

        //一段树的前序以及对应的中序遍历
        if (pre.length==0||in.length==0||pre.length!=in.length){
            return null;
        }

        //确定左子树和右子树的前序和中序
        TreeNode rootNode=new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if (in[i]==pre[0])
            {
                //左子树前序，中序
                rootNode.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                //右子树
rootNode.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
                break;
            }
        }
        return rootNode;
    }