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

Note:

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

 

 to see which companies asked this question

 

 

递归就可以了。

 

#include
      
       using namespace std;/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    TreeNode* buildTree(vector
       
        & preorder, vector
        
         & inorder) {        if(preorder.size()==0||inorder.size()==0||find(inorder.begin(),inorder.end(),preorder[0])==inorder.end())            return NULL;        auto rootindex=find(inorder.begin(),inorder.end(),preorder[0]);        TreeNode *root = new TreeNode(preorder[0]);        vector
         
           subleft,subright;        preorder.erase(preorder.begin());        if(rootindex!=inorder.begin())            subleft.insert(subleft.begin(),inorder.begin(),rootindex);        if(rootindex!=inorder.end()-1)            subright.insert(subright.begin(),rootindex+1,inorder.end());           root->left=buildTree(preorder,subleft);           root->right=buildTree(preorder,subright);           return root;    }};