Question：

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:



You may assume that duplicates do not exist in the tree.

Anwser 1 ：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *build(vector<int> &preorder, vector<int> &inorder, int sPre, int ePre, int sMid, int eMid) {
        if (sPre > ePre || sMid > eMid) return NULL;
        
        int pivot = preorder[sPre];
        
        int pos;
        for (pos = sMid; pos <= eMid; pos++) {
            if (inorder[pos] == pivot)
                break;
        }
        
        TreeNode *parent = new TreeNode(pivot);
        
        parent->left  = build(preorder, inorder, sPre + 1, sPre + (pos - sMid), sMid, pos - 1);
        parent->right = build(preorder, inorder, sPre + (pos - sMid) + 1, ePre, pos + 1, eMid);
        
        return parent;
    }
    
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
};

Anwser 2 ：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = preorder.size();
        if(size == 0) return NULL;        
        return BuildBT(preorder, inorder, 0, 0, size-1);
    }

    TreeNode *BuildBT(vector<int> &preorder, vector<int> &inorder, int pos, int start, int end){
        if(start > end ) return NULL;  
        
        int j = std::find(inorder.begin() + start, inorder.end() + end, preorder[pos]) - inorder.begin();

        TreeNode *root = new TreeNode(inorder[j]);
        root->left = BuildBT(preorder, inorder, pos+1, start, j-1);
        root->right = BuildBT(preorder, inorder, j+pos-start+1, j+1, end); // j+pos-start+1 is the relative position in the preorder array of the  next right child   
        
        return root;
    }
};