106. Construct Binary Tree from Inorder and Postorder Traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void createMapping(vector<int>&in, unordered_map<int, int> &m)
    {
        for(int i=0; i<in.size(); i++)
        {
            m[in[i]] = i;
        }
    }

    TreeNode* solve(vector<int>&post, int &index, int s, int e, unordered_map<int, int> &nodeToIndex)
    {
        if(index < 0 || s > e)
        {
            return NULL;
        }

        int position = nodeToIndex[post[index]];

        TreeNode* temp = new TreeNode(post[index--]);

        //first we call subtree because travesing from end to start

        temp -> right = solve(post, index, position+1, e, nodeToIndex);

        temp -> left = solve(post, index, s, position-1, nodeToIndex);

        return temp;
        
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //to traverse postorder from the right side because last index is the root node
        int i = postorder.size()-1;
        unordered_map<int, int> nodeToIndex;

        createMapping(inorder, nodeToIndex);

        return solve(postorder, i, 0, postorder.size()-1, nodeToIndex);
    }
};