题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复的数字。

前序遍历指的是先遍历根节点再分别遍历左右子节点；中序遍历指的是先遍历左子结点，其次根节点，最后右子节点。

思路很简单，先根据前序遍历的结果确定根节点，再在中序遍历的结果中查找到该节点，这样就可以切分出左右子树序列，在得到的左右子树序列中递归使用上面的方法即可构建出原来的树。

遍历序列
遍历序列

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    return build(pre, in);
}

private TreeNode build(int [] pre, int [] in) {
    if (pre.length == 0 || in.length == 0) {
        return null;
    }
    TreeNode root = new TreeNode(pre[0]);
    // 寻找根节点
    int pos = findRoot(in, root.val);
    
    int [] pre_tmp = copy(pre, 1, pos);
    int [] in_tmp = copy(in, 0, pos - 1);
    // 递归完成左子树的建立
    root.left = build(pre_tmp, in_tmp);
    
    pre_tmp = copy(pre, pos + 1, pre.length - 1);
    in_tmp = copy(in, pos + 1, in.length - 1);
    // 递归完成右子树的建立
    root.right = build(pre_tmp, in_tmp);
    
    return root;
}

// 遍历中序遍历序列寻找根节点
private int findRoot(int [] in, int val) {
    for (int i = 0; i < in.length; i ++) {
        if (in[i] == val) {
            return i;
        }
    }
    return 0;
}

// 复制数组用于下一步操作
private int[] copy(int [] array, int start, int end){
    int length = end - start + 1;
    int [] res = new int[length];
    for (int i = 0; i < length; i ++){
        res[i] = array[i + start];
    }
    return res;
}

整体而言，算法使用了O(nlogn)的辅助空间，时间复杂度是O(nlogn)。其实空间复杂度可以进一步优化，没必要使用新的数组来保存子树，只需要传递子树序列的开始和结束位置即可，不过这里我就不写了。

本来说话秋招准备之前写完大部分剑指 offer 题目的，结果发现 9 月份忙得很，现在找完了工作来填坑。