从中序和前序遍历序列构造二叉树
题目链接
class Solution {
public:
unordered_map<int,int> hash;
TreeNode* build(int rooti,int left,int right,vector<int>& preorder){
if(left > right)
return nullptr;
TreeNode* root = new TreeNode(preorder[rooti]);
int index = hash[preorder[rooti]];
root->left = build(rooti+1,left,index-1,preorder);
root->right = build(rooti+1+index-left,index+1,right,preorder);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i = 0;i < inorder.size();i++){
hash[inorder[i]] = i;
}
return build(0,0,preorder.size()-1,preorder);
}
};