面试题7：重建二叉树

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

class BinaryTreeNode{
    int value
    BinaryTreeNode left;
    BinaryTreeNode right;
}

思路：前序遍历获取根节点，中序遍历获取左、右子树的值，接着递归构建左、右子树。
解决方案：

public class Question7 {
    static class BinaryTreeNode {
        private final int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
        public BinaryTreeNode(int value){
            this.value = value;
        }
    }

    private static BinaryTreeNode constructCore(int[] preorder, int startPre, int endPre, int[] inorder, int startIn ,int endIn) {
        if (startPre > endPre || startIn > endIn) return null;
        // 通过前序遍历获取根节点
        BinaryTreeNode root = new BinaryTreeNode(preorder[startPre]);

        for (int i = 0; i<= inorder.length-1; i++){
            if (preorder[startPre] == inorder[i]){
                // 通过中序遍历获取左右子树
                root.left = constructCore(preorder, startPre + 1, startPre + i - startIn, inorder, startIn, i - 1);
                root.right = constructCore(preorder, i - startIn + startPre + 1, endPre, inorder, i + 1, endIn);
                break;
            }
        }
        return root;
    }

    // 前序遍历打印二叉树
    public static void preOrder(BinaryTreeNode binaryTreeNode){
        if (binaryTreeNode == null) return;
        System.out.println(binaryTreeNode.value);
        if (binaryTreeNode.left != null){
            preOrder(binaryTreeNode.left);
        }
        if (binaryTreeNode.right != null){
            preOrder(binaryTreeNode.right);
        }
    }

    public static void main(String[] args) {
        int[] preOrder = new int[]{1,2,4,7,3,5,6,8};
        int[] inOrder = new int[]{4,7,2,1,5,3,8,6};
        preOrder(constructCore(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1));
    }
}