Tuesday, September 23, 2014

Construct Binary Tree from Inorder and Postorder Traversal

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