2 approaches | Easy to comprehend | Detailed explanation | C++ | Java
Explanation:\nInorder Traversal -> First visit the left subtree, followed by the root node, followed by the right subtree.\nLeft -> Root -> Right\nPoint of obse
**Explanation:**\n**Inorder Traversal** -> First visit the left subtree, followed by the root node, followed by the right subtree.\n**Left -> Root -> Right**\nPoint of observation: The root node divides the inorder array into 2 halves, left subtree and right subtree.\n**Postorder Traversal** -> First visit left subtree, followed by the right subtree, followed bt the root node.\n**Left -> Right -> Root**\nPoint of observation: The root node is available at the end the of the postorder array. \n\nSo, as the first step, we can eaily obtain the value of the root node for the tree (or subtree) from the postorder array by accessessing the last element of the postorder array. Then, it can be observed that the root node divides the inorder array into two halves, the left and right subtree. So, for constructing the tree using postorder and inorder, we will find the find the index of root node in inorder array and then make recursive calls on the left and right subtrees.\n\n**Approach 1**\n\n**C++ 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    \n\t// variable key: \n\t// in -> inorder array\n\t// ins -> inorder start index\n\t// ine -> inorder end index\n\t// post -> postorder array\n\t// posts -> postorder start index\n\t// poste -> postorder end index\n\n    TreeNode* buildTreeUtil(vector<int>& in, int ins, int ine, vector<int>& post, int posts, int poste) {\n        \n        if(ins>ine || posts>poste) return nullptr;\n        \n        int rval=post[poste]; // root value\n        TreeNode* root = new TreeNode(rval);\n        \n        int i=ins;\n        while(in[i] != rval) i++;\n        \n        root->right = buildTreeUtil(in, i+1, ine, post, posts+i-ins, poste-1);\n        root->left = buildTreeUtil(in, ins, i-1, post, posts, posts+i-(ins+1));\n        return root;\n        \n    }\n    \n    TreeNode* buildTree(vector<int>& in, vector<int>& post) {\n        return buildTreeUtil(in, 0, in.size()-1, post, 0, post.size()-1);\n    }\n};\n```\n\n**Java Code:**\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n\n\t// variable key: \n\t// in -> inorder array\n\t// ins -> inorder start index\n\t// ine -> inorder end index\n\t// post -> postorder array\n\t// posts -> postorder start index\n\t// poste -> postorder end index\n        \n    public TreeNode buildTreeUtil(int[] in, int ins, int ine, int[] post, int posts, int poste) {\n        \n        if(ins>ine || posts>poste) return null;\n        \n        int rval=post[poste]; // root value\n        TreeNode root = new TreeNode(rval);\n        \n        int i=ins;\n        while(in[i] != rval) i++;\n        \n        root.right = buildTreeUtil(in, i+1, ine, post, posts+i-ins, poste-1);\n        root.left = buildTreeUtil(in, ins, i-1, post, posts, posts+i-(ins+1));\n        return root;\n        \n    }\n    \n    public TreeNode buildTree(int[] in, int[] post) {\n        return buildTreeUtil(in, 0, in.length-1, post, 0, post.length-1);\n    }\n}\n```\n\n\n****Approach 2****\nNote: (As given in the problem description)\nYou may assume that duplicates do not exist in the tree.\n\nSince we need not worry about the presence of duplicates in the tree, we can simply create an inorder key-value index map to store all values inside Hash Map and easily access the index of any particular node in the inorder traversal of the tree.\n\n**C++ 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    unordered_map<int,int> mp;\n    TreeNode* buildTreeUtil(vector<int>& post, int& idx, const int& si, const int& ei) {\n        if (si>ei) return NULL;\n        TreeNode* root = new TreeNode(post[idx]);\n        int mid = mp[post[idx]];\n        idx--;\n        root->right = buildTreeUtil(post, idx, mid+1, ei);\n        root->left = buildTreeUtil(post, idx, si, mid-1);\n        return root;\n    }\n\n    TreeNode* buildTree(vector<int>& in, vector<int>& post) {\n        for(int i=0; i<in.size(); i++) mp[in[i]]=i;\n        int idx=post.size()-1;\n        return buildTreeUtil(post, idx, 0, in.size()-1);\n    }\n};\n```\n\n**Java Code:**\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    \n    public TreeNode buildTreeUtil(int[] post, int idx, int si, int ei, Map<Integer, Integer> mp) {\n        \n        if (si>ei) return null;\n        TreeNode root = new TreeNode(post[idx]);\n\n        int mid = mp.get(post[idx]);\n        idx--;\n\n        root.right = buildTreeUtil(post, idx, mid+1, ei, mp);\n        root.left = buildTreeUtil(post, idx-(ei-mid), si, mid-1, mp);\n        return root;\n    }\n\n    public TreeNode buildTree(int[] in, int[] post) {\n        \n        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();\n        for(int i=0; i<in.length; i++) mp.put(in[i], i);\n        return buildTreeUtil(post, post.length-1, 0, in.length-1, mp);\n        \n    }\n}\n```
[]