本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
题目来源https://www.acwing.com/problem/content/23/
思路:这是很经典的题，根据前序遍历创建根节点，再通过递归创建左右子树，最后根节点指向左右子树。
具体做法是通过在中序遍历中找到根节点的位置k，分别得到中序遍历左右子树的区间，得到左右区间的长度l,r。
而前序遍历的左子树位置是从根节点接着的l个节点，右子树区间是左子树的下一个节点到最后的节点。
中序遍历遍历找位置用个map即可。由于每个节点只创建一次，时间复杂度o(n)。
/**
* 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:
map<int,int>m;
vector<int>preorder,inorder;
TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
preorder=_preorder,inorder=_inorder;
for(int i=0;i<_inorder.size();i++){
m[_inorder[i]]=i;
}
return dfs(0,_preorder.size()-1,0,_inorder.size()-1);
}
TreeNode* dfs(int pl,int pr,int il,int ir){
if(pl>pr)return NULL;
TreeNode* root=new TreeNode(preorder[pl]);
int k=m[root->val];
auto left=dfs(pl+1,pl+1+k-il-1,il,k-1);
auto right=dfs(pl+k-il+1,pr,k+1,ir);
root->left=left;root->right=right;
return root;
}
};
