✅[C++] EASY Intuitive Sol | Clean Recursive Code w/ Explanation (Dry Run) | T.C:O(N)
Hello everyone! I hope you all are doing great.\n\nNote: Please do upvote if you find this post helpful!\nNote: Some people are unethically downvoting my post, 
Hello everyone! I hope you all are doing great.\n\n***Note: Please do upvote if you find this post helpful!***\n**Note: Some people are unethically downvoting my post, please do upvote and save this post from disappearing**\n\nNow, we want to create our binary tree with given postorder and inorder traversals.\n\n**Observations:**\n1. *Inorder* is `LEFT ROOT RIGHT`. So for any node lets say current node is at index `i` in inorder array, if you think it as a root of its subtree, then all the nodes at indices less than `i` will be on the left subtree of the current node and all the nodes at indices greater than `i` will be on the right subtree of the current node.\n\n2. *Postorder* is `LEFT RIGHT ROOT`. So the **last element** of our postorder array will always be our `root`, and then we will move backwards in our postorder array to find the next root.\n\n**My Approach:**\n1. Since Post Order traversal is like `LEFT RIGHT ROOT`, therefore we will traverse the postorder array from backwards and will construct our tree like `ROOT RIGHT LEFT`.\n\n2. Take our node from postorder array, let say it is at index `idx` (We came from `postorder.size()-1` to `idx`) and this will be our root in current recursive call, then decrement the `idx` for our next upcoming root.\n\n3. Now find our current node (from step 2) in our inorder array (let say we found it at `i`), then we will have nodes in left subtree of current node who are at position less than `i` and nodes in right subtree of current node who are at position greater than `i`.\n\n4. So we make a recursive call to construct the right subtree first, then we make a recursive call to construct the left subtree of our current node. (Since we are building our Binary Tree in `ROOT RIGHT LEFT`).\n\n**DRY RUN for algo explained above:**\n\n**Initial Situtation: (Step 1)** \n```\nInorder array: [9,3,15,20,7]\nPostorder  array: [9,15,7,20,3]\n\nHence 3 will be our root and inorder range for left subtree will be [9] and inorder range for right subtree will be [15, 20, 7]\n\n\t\t\t3\n\t\t  /\t  \\\n\t   [9]    [15, 20, 7]   -> Inorder\n\t   [9]    [15, 7, 20]   -> Postorder\n```\n\n**Step 2:**\n```\n\t\t\t3\n\t\t /\t    \\\n\t\t9\t    20\n\t   / \\\t    /  \\\n\t  *   *  [15] [7] -> Inorder\n\t\t\t [15] [7] -> Postorder\n```\n\n**Step 3:**\n```\n\t\t\t3\n\t\t /\t    \\\n\t\t9\t    20\n\t   / \\\t   /  \\\n\t  *   *   15   7\n\t\t\t / \\  / \\\n\t\t\t * *  * *\n```\n\n**Below is the code for the approach I gave above:**\n\n```\nclass Solution {\npublic:\n    unordered_map<int, int>mp; // Stores (node -> index in inorder array)\n    \n    TreeNode* make_tree(int start, int end, int &idx, vector<int>& postorder, vector<int>& inorder){\n        \n\t\t// If range for inorder is NOT valid then return NULL\n        if(start > end) return NULL;\n        \n\t\t// Create a node for our root node of current subtree\n        TreeNode* root = new TreeNode(postorder[idx]);\n        \n\t\t// Find position of current root in inorder array\n        int i = mp[root->val];\n\t\t\n\t\t// Decrement our pointer to postorder array for our next upcoming root if any\n        idx--;\n\t\t\n\t\t// Make a call to create right subtree, inorder range [i+1, end]\n        root->right = make_tree(i+1, end, idx, postorder, inorder);\n\t\t\n\t\t// Make a call to create left subtree, inorder range [start, i-1]\n        root->left = make_tree(start, i-1, idx, postorder, inorder);\n        \n        return root;\n    }\n    \n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        int idx=postorder.size()-1;\n        \n\t\t// Create (nodes -> index of inorder array) mapping\n        for(int i{}; i<inorder.size(); ++i){\n            \n            mp[inorder[i]] = i;\n        }\n\t\t// Create tree starting from root at position (n-1) in postorder array\n\t\t// Range for current inirder array : [0, n-1]\n        return make_tree(0, inorder.size()-1, idx, postorder, inorder);\n    }\n};\n```\n\n**Time Complexity:** ***O(N)*** since we are visiting every node from postorder array at once and creating a node for it.\n\n**Space Complexity:** ***O(N)*** since we are creating a mapping for every node that will contain its index for a node in inorder array.\n\n***NOTE: Please do \u2705 Upvote if you like my solution!***
[]