forked from larissalages/code_problems
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path105.cpp
More file actions
25 lines (21 loc) · 866 Bytes
/
105.cpp
File metadata and controls
25 lines (21 loc) · 866 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
unordered_map<int, int > mp;
public:
TreeNode* buildTree_util(vector<int>& preorder, int pre1, int pre2 , vector<int>& inorder, int i1, int i2) {
if(pre1 > pre2 || i1 > i2)
return NULL;
TreeNode *root = new TreeNode(preorder[pre1]);
int diff = mp[preorder[pre1]] - i1;
root->left = buildTree_util(preorder, pre1 + 1, pre1+diff, inorder, i1, i1+diff-1);
root->right = buildTree_util(preorder, pre1 +diff+1, pre2 , inorder, i1+diff+1, i2);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = inorder.size();
if(n == 0)
return NULL;
for(int i = 0; i < n; i++)
mp[inorder[i]] = i;
return buildTree_util(preorder, 0, n-1, inorder,0, n-1);
}
};