[C++] 2 Simple solutions (W/ Explanation)
Hello everyone, firstly thanks for refering to my post in advance :)\nNote : If you like my solutions and explanation, please UPVOTE! (Please Support if you can
Hello everyone, firstly thanks for refering to my post in advance :)\nNote : If you like my solutions and explanation, **please UPVOTE!** (Please Support if you can, as it motivates me to post solutions everyday. Please do not downvote)\n\nSo, the basic idea is same for all the approaches. \n* In **inorder** the order is : ***left->root->right***. \n* In **postorder** the order is : ***left->right->root***.\n* So in the postOrder array, the last of \'n\' number of nodes is always the root of a subtree. \n* So, we begin with the last element of the \'postorder\' array as the root and search for that element in inorder vector. \n* In inorder, the root is always at the center. Hence when we find the element we\'re looking for, we can say that all the elements on its left in the array are in it\'s left subtree and those on it\'s right are in it\'s right subtree.\n* So, we recursively find a root from the \'postorder\' array, search for it in the \'inorder\' array, nmake it the root and construct it\'s left and right subtrees.\n\n**APPROACH - 1 :** ***Simple Recursion (Without Using Map)***\n\n   **Time Complexity :** O(n^2), where n = length of inorder or postorder array.\n   \n   **Code :**\n```\nclass Solution {\nprivate:\n    int curr;\npublic:\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        int n = inorder.size();\n        curr = n-1;\n        return constructTree(inorder, postorder, 0, n-1);\n    }\n    \n    TreeNode* constructTree(vector<int>&in, vector<int>&post, int start, int end){\n        if(start > end) return NULL;\n        \n        int i = find(in.begin(), in.end(), post[curr]) - in.begin();\n        \n        curr--;\n        TreeNode *head = new TreeNode(in[i]);\n        head->right = constructTree(in, post, i+1, end);\n        head->left = constructTree(in, post, start, i-1);\n        \n        return head;\n        \n    }\n};\n```\n\n**APPROACH - 2 :** ***Recursion with Map***\nUsing the map to strore the indices, we\'re optimizing the code to make it to O(n) time complexity.\n  **Time Complexity :** O(n)\n  \n  **Code :**\n```\nclass Solution {\nprivate:\n    map<int, int> m;\npublic:\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        int n = inorder.size(), p=n-1;\n        for(int i=0;i<n;i++) m[inorder[i]] = i;\n        return constructTree(inorder, postorder, 0, n-1, p);\n    }\n    \n    TreeNode* constructTree(vector<int>&in, vector<int>&post, int l, int r, int &idx)     {\n        if(l > r) return NULL;\n        \n        TreeNode *root = new TreeNode(post[idx--]);\n        int i=m[root->val];\n        root->right = constructTree(in, post, i+1, r, idx);\n        root->left = constructTree(in, post, l, i-1, idx);\n        \n        return root;\n        \n    }\n};\n```\n\nIf you like my solutins, **please UPVOTE!!**\n\n\n   \n
['Recursion', 'C', 'C++']