一. 思路

按照纸质考试去思考很容易知道怎么解。转成代码实现应该要了解如下递归解法的模板：

public TreeNode rebuild(...) {
    if (!...) return null;
    TreeNode root = new TreeNode(...);
    node.left = rebuild(...);
    node.right = rebuild(...);
    return root;
}

public TreeNode reConstructBTree(...) {
    return rebuild(...);
}

二. 代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return rebuild(pre, 0, pre.length-1, in, 0, in.length-1);
    }

    public TreeNode rebuild(int[] pre, int preLeft, int preRight,
                           int[] in, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preLeft]);
        int rootIndex = inLeft;
        while (rootIndex <= inRight && in[rootIndex] != pre[preLeft]){
            rootIndex++;
        }
        root.left = rebuild(pre, preLeft+1, preLeft+rootIndex-inLeft,
                           in, inLeft, rootIndex-1);
        root.right = rebuild(pre, preLeft+rootIndex-inLeft+1, preRight,
                            in, rootIndex+1, inRight);
        return root;
    }
}