1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
unordered_map<int, int> hashTable;
for(int i =0;i<inorder.size();++i){
hashTable.insert({inorder[i],i});
}
return dfs(preorder,inorder,hashTable,0,0,inorder.size()-1);
}
TreeNode* dfs(vector<int>& preorder,vector<int>& inorder,unordered_map<int, int>& hashTable,int pIndex, int iLeftIndex, int iRightIndex){
if(iLeftIndex>iRightIndex){
return nullptr;
}
TreeNode * node =new TreeNode(preorder[pIndex]);
int iRootIndex =hashTable[preorder[pIndex]];
node->left =dfs(preorder,inorder,hashTable,pIndex+1,iLeftIndex,iRootIndex-1);
node->right=dfs(preorder,inorder,hashTable,pIndex+iRootIndex-iLeftIndex+1,iRootIndex+1,iRightIndex);
return node;
}
};
|
