题目描述：
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：
3 / \ 9 20 / \ 15 7
代码：
/**
* 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<int>& preorder, vector<int>& inorder) {
return CreateTree(0,preorder.size()-1,0,inorder.size(),preorder,inorder);
}
TreeNode* CreateTree(int pre_begin,int pre_end,int in_begin,int in_end,vector<int>&pre,vector<int>&ino)
{
if(in_begin>in_end||pre_begin>pre_end) return NULL;
TreeNode *root=new TreeNode(pre[pre_begin]);
int count=in_begin;
while(count<=in_end&&pre[pre_begin]!=ino[count])count++;
root->left=CreateTree(pre_begin+1,count-in_begin+pre_begin,in_begin,count-1,pre,ino);
root->right=CreateTree(count-in_begin+pre_begin+1,pre_end,count+1,in_end,pre,ino);
return root;
}
};
执行效率：
执行用时：48 ms, 在所有 C++ 提交中击败了40.71%的用户
内存消耗：17.5 MB, 在所有 C++ 提交中击败了42.42%的用户
