105.从前序与中序遍历序列构造二叉树

``````class Solution {
public:
TreeNode* dfs(vector<int>& preorder,int prebeg,int preend,vector<int>& inorder,int inbeg,int inend){
if(prebeg == preend) return nullptr;
int tmp = preorder[prebeg];
TreeNode* root = new TreeNode(tmp);
if(preend - prebeg == 1) return root;

//切割点
int index;
for(index = inbeg;index < inend;index++){
if(inorder[index] == tmp) break;
}

//切割
int leftinbeg = inbeg;
int leftinend = index;
int rightinbeg = index+1;
int rightinend = inend;

int leftprebeg = prebeg+1;
int leftpreend = leftprebeg +index - inbeg;
int rightprebeg = leftpreend;
int rightpreend = preend;
root->left = dfs(preorder,leftprebeg,leftpreend,inorder,leftinbeg,leftinend);
root->right = dfs(preorder,rightprebeg,rightpreend,inorder,rightinbeg,rightinend);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size() == 0 || inorder.size() == 0) return nullptr;
return dfs(preorder,0,preorder.size(),inorder,0,inorder.size());
}
};``````

THE END