https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inMap = new HashMap<Integer, Integer>();

    for(int i = 0; i < inorder.length; i++) {
        inMap.put(inorder[i], i);
    }

    TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
    return root;
}

public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
    if(preStart > preEnd || inStart > inEnd) return null;

    TreeNode root = new TreeNode(preorder[preStart]);
    int inRoot = inMap.get(root.val);
    int numsLeft = inRoot - inStart;//root的左子節(jié)點(diǎn)的數(shù)量

    root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);
//在前序遍歷對(duì)應(yīng)的vector中牲尺，如果root有左子節(jié)點(diǎn)的話那么對(duì)應(yīng)的為vector中它對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)
    root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap);
//在前序遍歷對(duì)應(yīng)的vector中伴挚，如果root有右節(jié)點(diǎn)的話遮婶，那么對(duì)應(yīng)的右節(jié)點(diǎn)在vector中的索引為preStart + numsLeft + 1(numsLeft 是左節(jié)點(diǎn)的數(shù)量)
    return root;
}

另外一種不使用遞歸的算法

class Solution {                                                        
public:
    TreeNode* buildTree(vector<int> &pre, vector<int> &in) {           
           int i = 0, j = 0;
           TreeNode *root = new TreeNode(0x80000000);
           TreeNode *pp = NULL,*ptr = root;
           stack<TreeNode*> sn;
           sn.push(root);
        
           while (j<in.size()) {
            if(sn.top()->val == in[j]){//當(dāng)該節(jié)點(diǎn)與 中序遍歷的j節(jié)點(diǎn)相同說(shuō)明 當(dāng)前前序遍歷數(shù)組中的i(即當(dāng)前棧頂節(jié)點(diǎn)對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn))所對(duì)應(yīng)的節(jié)點(diǎn)為sn棧頂節(jié)點(diǎn)的右節(jié)點(diǎn)
                                       //即相當(dāng)于當(dāng)前的棧頂節(jié)點(diǎn)已經(jīng)”鏈接“上了左節(jié)點(diǎn)那么下一個(gè)索引i對(duì)應(yīng)的節(jié)點(diǎn)應(yīng)為該節(jié)點(diǎn)的右節(jié)點(diǎn)                      
               pp = sn.top();
                sn.pop();
                j++;
            }else if(pp){
                ptr = new TreeNode(pre[i]);
                pp->right = ptr;
                pp = NULL;
                sn.push(ptr);
                i++;
            }else{//一直左左左
                ptr = new TreeNode(pre[i]);
                sn.top()->left = ptr;
                sn.push(ptr);
                i++;
            }
          }      
          ptr = root->left;
          delete root;
          return ptr;
    }
};