Thursday, May 7, 2015

[LeetCode] 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.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(unordered_map<int, int> &map,
                        vector<int> &postorder,int ps, int pe, 
                        vector<int> &inorder, int is, int ie) 
    {
        if(ps>pe) return NULL;
        int i= map[postorder[pe]];
        TreeNode *node = new TreeNode(postorder[pe]);
        node->left = buildTree(map,postorder, ps, ps+i-is-1, inorder, is, i-1);
        node->right = buildTree(map,postorder, ps+i-is, pe-1, inorder, i+1, ie);
        return node;
    }

    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        unordered_map<int, int> map;
        for(int i=0;i<inorder.size();i++)
        {
            map[inorder[i]] = i;
        }
        int len = postorder.size();
        return buildTree(map, postorder, 0, len-1, inorder, 0, len-1);
    }
};