105. Construct Binary Tree from Preorder and Inorder Traversal
难度: Medium
刷题内容
原题连接
- https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
内容描述
``` 根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：
3
/ \ 9 20 / \ 15 7 ```
解题方案
思路 1
和106思路一致
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int start, int end, int& index){
int post = preorder[index];
int i=start;
for(;i<end;i++)
if(post == inorder[i])
break;
TreeNode* node = new TreeNode(post);
if(i>start)
node->left = dfs(preorder, inorder, start, i-1, ++index);
if(i<end)
node->right = dfs(preorder, inorder, i+1, end, ++index);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty()||inorder.empty())
return NULL;
int index =0;
return dfs(preorder, inorder, 0, preorder.size()-1, index);
}
