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

力扣题目链接(opens new window)

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

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());}
};