Easy Explanation of the Code // C++ // Recursive Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind this solution is since the postOrder store the root node ( top mos
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n***The intuition behind this solution is since the postOrder store the root node ( top most node of tree) at its last index . from traversing reverse we get our root node, from this I can easily find the right and left subtree from the Inorder . From this data that we have we can crete our tree by joining first rightSubtree to root node and then leftSubtree to it.***\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. The code defines a class `Solution` that contains a function `buildTree` to construct a binary tree from its inorder and postorder traversal sequences.\n\n2. The binary tree nodes are represented using the `TreeNode` struct, which has an integer value (`val`) and pointers to its left and right children (`left` and `right`).\n\n3. The `buildTree` function takes two input vectors, `inorder` and `postorder`, representing the inorder and postorder traversal sequences of the binary tree, respectively.\n\n4. Inorder traversal visits the left subtree first, then the root node, and finally the right subtree. Postorder traversal visits the left subtree first, then the right subtree, and finally the root node.\n\n5. The `buildTree` function initializes variables `size`, `postIndex`, `start`, and `end` to keep track of the tree size, current index in the `postorder` vector, and the start and end indices of the `inorder` subarray being processed, respectively.\n\n6. It also uses an unordered map `mp` to store the indices of elements in the `inorder` vector. This map allows quick lookup of an element\'s position in the `inorder` sequence.\n\n7. The main logic of tree construction is implemented in the `solver` function, which is a recursive helper function.\n\n8. The `solver` function takes the `postorder` and `inorder` vectors, along with the previously mentioned variables (`size`, `postIndex`, `start`, `end`, and `mp`), to construct the binary tree.\n\n9. In the `solver` function, it checks if the `postIndex` is out of bounds or if the `start` index exceeds the `end` index. If either condition is true, it means the current subtree is empty, and it returns `NULL`.\n\n10. Otherwise, it takes the element at `postIndex` from the `postorder` vector, creates a new node with this element, and decrements `postIndex`.\n\n11. It then finds the position (index) of this element in the `inorder` vector using the precomputed indices stored in the `mp` map.\n\n12. Next, it calls `solver` recursively to build the right subtree, passing the appropriate indices for the right subarray of `inorder`.\n\n13. Similarly, it constructs the left subtree using recursive calls to `solver` and passing the appropriate indices for the left subarray of `inorder`.\n\n14. The `solver` function returns the current node, and this node becomes the right or left child of its parent node in subsequent recursive calls.\n\n15. Finally, the `buildTree` function returns the root of the constructed binary tree.\n\nIn summary, the code efficiently constructs a binary tree from its inorder and postorder traversal sequences using a recursive approach with the aid of an unordered map for faster element position lookup. The recursive `solver` function handles the tree construction for each subtree, and the construction starts from the last element of the postorder sequence and proceeds backward.\n\n# Complexity\n- Time complexity:O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n***----------------Please UpVote if you really find heplfull-----------***\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    TreeNode* solver(vector<int> &postorder,vector<int> &inorder,int size,int &postIndex,int start,int end,     unordered_map<int,int>  &mp)\n   {\n       if(postIndex<0 || start>end)\n       {\n           return NULL;\n       }\n\n       int element=postorder[postIndex];\n       postIndex--;\n       int pos= mp[element];\n       TreeNode* root=new TreeNode(element);\n       root->right=solver(postorder,inorder,size,postIndex,pos+1,end,mp);\n       root->left= solver(postorder,inorder,size,postIndex,start,pos-1,mp); \n       return root;\n       \n   }\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        int size=postorder.size();\n        int postIndex=size-1;\n        int start=0;\n        int end=size-1;\n        unordered_map<int,int>  mp;\n        for(int i=0;i<size;i++)\n        {\n            mp[inorder[i]]=i;\n        }\n\n        TreeNode* root=solver(postorder,inorder,size,postIndex,start,end,mp);\n        return root;\n    }\n};\n```
['Tree', 'Binary Tree', 'C++']