自己做行程的网站/宁波seo排名外包公司

思路：前序遍历第一个肯定是当前树的根节点，中序遍历找到这个根节点的位置，起左边为他的左子树，右边为他的右子树，我们用map记录根节点在中序遍历中对应的位置，然后我们递归的去找每个根节点的左右子树重构二叉树。

代码：

/*** 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> mp;vector<int> preorder,inorder;TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {preorder=_preorder;inorder=_inorder;for(int i=0;i<_inorder.size();i++) mp[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 nullptr;TreeNode* root=new TreeNode(preorder[pl]);int k=mp[preorder[pl]];TreeNode* left=dfs(pl+1,pl+k-il,il,k);TreeNode* right=dfs(pl+k-il+1,pr,k+1,ir);root->left=left,root->right=right;return root;}
};