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

Note:

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

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:template
     
      void creatTree(TreeNode *&root, Iter preBeg,Iter preEnd,Iter inBeg,Iter inEnd){    if (preBeg==preEnd||inBeg==inEnd)    {        root=NULL;        return;    }    root=new TreeNode(*preBeg);    vector
      
       ::iterator tmp=find(inBeg,inEnd,*preBeg);    int leftsize=tmp-inBeg;    creatTree(root->left, preBeg+1,preBeg+leftsize+1,inBeg,tmp);    creatTree(root->right, preBeg+leftsize+1,preEnd,tmp+1,inEnd);}TreeNode *buildTree(vector
       
         &preorder, vector
        
          &inorder) {    TreeNode *root;    creatTree(root,preorder.begin(),preorder.end(),inorder.begin(),inorder.end());    return root;}/*TreeNode * creatTree(vector
         
          ::iterator preBeg,vector
          
           ::iterator preEnd,vector
           
            ::iterator inBeg,vector
            
             ::iterator inEnd){ if (preBeg==preEnd||inBeg==inEnd) { return NULL; } TreeNode *root=new TreeNode(*preBeg); vector
             
              ::iterator tmp=find(inBeg,inEnd,*preBeg); int leftsize=tmp-inBeg; root->left=creatTree(preBeg+1,preBeg+leftsize+1,inBeg,tmp); root->right=creatTree(preBeg+leftsize+1,preEnd,tmp+1,inEnd); return root;}TreeNode *buildTree(vector
              
                &preorder, vector
               
                 &inorder) { return creatTree(preorder.begin(),preorder.end(),inorder.begin(),inorder.end());}*/};