两种方法：

一、递归

有先序序列得到根节点的值，创建根节点，再递归构造左子树，右子树。 由先序得到根结点，再在中序序列找到根节点，根节点左边就是左子树，右边就是右子树。

在中序序列中找根节点，就可以用到哈希结构，这里是想得到她的坐标，所以value存坐标。

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer,Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder,int[] inorder,int preLeft,int preRight,int inLeft,int inRight){
        if(preLeft>preRight||inLeft>inRight) return null;
        int pre_rootindex=preLeft;
        int in_rootindex=indexMap.get(preorder[preLeft]);
        TreeNode root=new TreeNode(preorder[preLeft]);
        root.left=myBuildTree(preorder,inorder,preLeft+1,in_rootindex-inLeft+pre_rootindex,inLeft,in_rootindex-1);
        root.right=myBuildTree(preorder,inorder,in_rootindex-inLeft+pre_rootindex+1,preRight,in_rootindex+1,inRight);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n=preorder.length;
        indexMap=new HashMap<Integer,Integer>();
        for(int i=0;i<n;i++){
            indexMap.put(inorder[i],i);
        }
        return myBuildTree(preorder,inorder,0,n-1,0,n-1);
    }
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private: unordered_map<int,int> indexMap;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
         int n=preorder.size();
        //indexMap=new HashMap<Integer,Integer>();
        for(int i=0;i<n;i++){
            indexMap.emplace(inorder[i],i);
        }
        return myBuildTree(preorder,inorder,0,n-1,0,n-1);
    }
     TreeNode* myBuildTree(vector<int> preorder,vector<int> inorder,int preLeft,int preRight,int inLeft,int inRight){
        if(preLeft>preRight||inLeft>inRight) return nullptr;
        int pre_rootindex=preLeft;
        int in_rootindex=indexMap.at(preorder[preLeft]);
        TreeNode *root=new TreeNode(preorder[preLeft]);
        root->left=myBuildTree(preorder,inorder,preLeft+1,in_rootindex-inLeft+pre_rootindex,inLeft,in_rootindex-1);
        root->right=myBuildTree(preorder,inorder,in_rootindex-inLeft+pre_rootindex+1,preRight,in_rootindex+1,inRight);
        return root;
    }
};

二、迭代，用到栈

先序：根左右   <-

中序：左根右   -> 

题解见https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--22/ 

补充：当先序与中序相等时，此结点为某结点的右子树，寻找父节点的方法是：倒序遍历先序（栈中的先序），正序遍历中序，两者最后一个相等的结点即为父节点.

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||preorder.length==0) return null;
        TreeNode root=new TreeNode(preorder[0]);
        Deque<TreeNode> stack=new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex=0;
        for(int i=1;i<preorder.length;i++){
            int preorderVal=preorder[i];//待判断的结点
            TreeNode node=stack.peek();//栈顶结点
            if(node.val!=inorder[inorderIndex]){//先序与中序不相等，则为左子树
                node.left=new TreeNode(preorderVal);
                stack.push(node.left);
            }
            else{//相等，则为某个节点的右子树，寻找该父节点
                while(!stack.isEmpty()&&stack.peek().val==inorder[inorderIndex]){
                    node=stack.pop();
                    inorderIndex++;
                }
                node.right=new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;

    }
}

 C++：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0||inorder.size()==0) return nullptr;
        stack<TreeNode*> sta;
        TreeNode* root=new TreeNode(preorder[0]);
        sta.push(root);
        int inorderIndex=0;
        for(int i=1;i<preorder.size();i++){
            TreeNode* node=sta.top();
            if(node->val!=inorder[inorderIndex]){
                node->left=new TreeNode(preorder[i]);
                sta.push(node->left);
            }
            else{
                while(!sta.empty()&&sta.top()->val==inorder[inorderIndex]){
                    node=sta.top();
                    sta.pop();
                    inorderIndex++;
                }
                node->right=new TreeNode(preorder[i]);
                sta.push(node->right);
            }
        }
        return root;
    }
};