步骤:

1. 通过根节点在前序遍历中的索引rootIndexAtPreorder找出根节点的值preorder[rootIndexAtPreorder]

2. 借助前面生成的HashMap, 通过根节点的值反向找出根节点在中序序列inorder中的索引

   rootIndexAtInorder = hashMap.get(preorder[rootIndexAtPreorder])

3. 通过根节点在中序序列中的索引值, 确定左子树和右子树的长度和边界

public class Solution { 
       class TreeNode {
        int val;
        TreeNode leftBorder;
        TreeNode rightBorder;

        TreeNode(int x) {
            val = x;
        }
    }
    int[] preorder;
    HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

    public TreeNode buildTreeBypreAndin(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            //hashMap用来存储中序遍历的值与索引的映射
            hashMap.put(inorder[i], i);
        }
        //整棵树的根节点为preorder中的第root号元素,左子树
        return recurByPreAndIn(0, 0, inorder.length - 1);
    }

    /**
     * @param rootIndexAtPreorder         根节点在前序遍历的索引
     * @param leftBorder                子树在中序遍历的左边界
     * @param rightBorder               子树在中序遍历的右边界
     * @return 返回回溯的根节点
     */
    private TreeNode recurByPreAndIn(int rootIndexAtPreorder, int leftBorder, int rightBorder) {
        //递归终止: 当leftBorder>rightBorder代表已经越过叶子节点,此时返回null
        if (leftBorder > rightBorder) {
            return null;
        }
        //建立根节点:preorder[rootIndexAtPreorder]表示根节点的值,root表示根节点在preorder数组中的序号
        TreeNode node = new TreeNode(preorder[rootIndexAtPreorder]);
        //查找根节点在中序遍历数组inorder中的序号,所以在前面将根节点的值作为key,根节点在inorder中的索引作为value保存在hashMap中
        Integer rootIndexAtInorder = hashMap.get(preorder[rootIndexAtPreorder]);
        //左子树递归;左递归中rootIndexAtPreorder表示根节点的左子节点,也就是左子树的根节点
        node.leftBorder = recurByPreAndIn(rootIndexAtPreorder + 1, leftBorder, rootIndexAtInorder - 1);
        //右子树递归; rootIndexAtPreorder + (rootIndexAtInorder - leftBorder)左子树长度 + 1
        node.rightBorder = recurByPreAndIn(rootIndexAtPreorder + rootIndexAtInorder - leftBorder + 1, rootIndexAtInorder + 1, rightBorder);
        //回溯返回根节点
        return node;
    }
}