C++ solution Using Recursion and Map with Explanation(90.33% faster)
Explanation:\nWe Using Unorder map to know the index of the ROOT element in INORDER element. that\'s why,we have to iterate all over the INORDER element and sav
**Explanation:**\nWe Using Unorder map to know the index of the ROOT element in INORDER element. that\'s why,we have to iterate all over the INORDER element and save their value and index in our **UNORDERED_MAP**; \nIt makes the solution **O(n)** instead of O(n^2).\n\n\nWe know that, the last element of **POSTORDER** array contains main **ROOT** Node. and In **INORDER** array we see that the left side of the **ROOT** element contains the **LEFT** side element and **Right** side contains all the **RIGHT** side element.\nSo, we have to find out the index of **ROOT** element in **INORDER** Element. \nSo, \n```int inorderIndex = m[postorder[postIndex]];```\nand Make ROOT =\n```TreeNode *root =new TreeNode(inorder[inorderIndex]);```\nand postIndex decreament by 1 for the next purpose.\nAnd then we go to the **Right side** first and make the **Right side** of the **ROOT**. Here the start index is inorderIndex+1 cause all Right Part is in the Right Side of the inorder Array.\n```root->right=solve(inorder,postorder,inorderIndex+1,end,postIndex);```\n\nAnd then we go to the **Left Side** and make the Left side of the **ROOT**. Here the end index is inorderIndex-1 cause all left Part is in the left Side of the inorder Array.\n```root->left=solve(inorder,postorder,start,inorderIndex-1,postIndex);```\n\nAnd Now the **base case**, when we stop our Recursion:\nWe all know when, start> end, we return NULL;\n``` if(start>end) return NULL;```\n\nAnd Last we return ROOT;\n\n**N:B: If you recurse Left Side first , it cause Runtime Error, cursed the code**\nCause,when you call left first the postindex got decreased in every call until left part finishes off but we are comparing from the last so need to get the last indexes for right part too that we will not be able to get it if we called for left part first.\nIf we call right part eventually postindex should decrease till left part so that we will be able to access parent node for every left tree element.\nHope this helps:)\n\n**Code:**\n\n```\nclass Solution {\npublic:\n unordered_map<int,int>m;\n    TreeNode* solve(vector<int>& inorder,vector<int>& postorder,int start,int end,int &postIndex){\n        if(start>end) return NULL;\n         int inorderIndex = m[postorder[postIndex]];\n\n        TreeNode* root = new TreeNode(inorder[inorderIndex]);    \n        \n        (postIndex)--;\n      root->right=solve(inorder,postorder,inorderIndex+1,end,postIndex);\n        root->left=solve(inorder,postorder,start,inorderIndex-1,postIndex);\n        \n        return root;\n    }\n    \n    \n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n\n        for(int i=0;i<inorder.size();i++){\n           m[inorder[i]] = i;\n            \n        }\n        int postIndex=postorder.size()-1;\n        return solve(inorder,postorder,0,postorder.size()-1,postIndex);\n    }\n};\n```\n**If you helped by this Explanation or Code or learn something from this, PLEASE UPVOTE**\nif I make any mistake , please comment and If you have better Idea please Comment. Thank you for Reading.
['Recursion', 'C', 'C++']