重建二叉树

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

解题思路：
前序遍历第一个结点是父结点，中序遍历如果遍历到父结点，那么父结点前面的结点是左子树的结点，后边的结点的右子树的结点，这样可以找到左、右子树的前序遍历和中序遍历，可以用同样的方法去构建左右子树，可以用递归完成。

• 也即是说，以上述中前序遍历序列{1}为根节点，而中序遍历序列中{4 , 7 , 2}为左子树结点，{5 , 3 , 8 , 6}为右子树结点。
• 接着，以前序遍历序列中{2}为左子树的一个根节点，遍历{4 , 7 , 2}得到 , {4 , 7}为左子树以{2}这个根节点下的左子树，而右侧没有，则为空。
• 以此类推。

java代码实现：

public class SortClass {

    public static void main(String[] args){
        int[] preorder = {1,2,4,7,3,5,6,8};
        int[] inorder = {4,7,2,1,5,3,8,6};
        try {
            BinaryTreeNode binaryTreeNode= constructCore(preorder,inorder);
            System.out.println(binaryTreeNode);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    private static class BinaryTreeNode {

        public int value;
        public BinaryTreeNode leftNode;
        public BinaryTreeNode rightNode;

        @Override
        public String toString() {
            return "BinaryTreeNode{" +
                    "value=" + value +
                    ", leftNode=" + leftNode +
                    ", rightNode=" + rightNode +
                    '}';
        }
    }
    private static BinaryTreeNode constructCore(int[] preorder, int[] inorder) throws Exception {
        if (preorder == null || inorder == null) {
            return null;
        }
        if (preorder.length != inorder.length) {
            throw new Exception("长度不一样，非法的输入");
        }
        BinaryTreeNode root = new BinaryTreeNode();
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                root.value = inorder[i];
                System.out.println(root.value);
                root.leftNode = constructCore(Arrays.copyOfRange(preorder, 1, i + 1),
                        Arrays.copyOfRange(inorder, 0, i));
                root.rightNode = constructCore(Arrays.copyOfRange(preorder, i + 1, preorder.length),
                        Arrays.copyOfRange(inorder, i + 1, inorder.length));
            }
        }
        return root;
    }
}