Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
if (postorder.size()==0) return NULL;
else
{
unordered_map<int, int> idxMap;
int len = inorder.size();
for (int i=0; i<len; i++)
{
idxMap[inorder[i]]=i;
}
int n = inorder.size()-1;
return helper(inorder, postorder,0, n, n, idxMap);
}
}
TreeNode *helper( vector<int> &inorder, vector<int> &postorder,int start, int end, int rIdx, unordered_map<int, int> &map)
{
if (start>end)
return NULL;
TreeNode *r = new TreeNode(postorder[rIdx]);
int mid=map[postorder[rIdx]];
r->left = helper(inorder,postorder,start,mid-1,rIdx-1-(end-mid), map);
// This index is what takes me most of time to figure out, need to find a way to rationalize it.
r->right = helper(inorder,postorder,mid+1,end,rIdx-1, map);
return r;
}
};
No comments:
Post a Comment