Easy C++ solution using recursion📊📊
To solve the problem of constructing a binary tree from its inorder and postorder traversals, we can use a recursive approach similar to the previous one for pr
To solve the problem of constructing a binary tree from its inorder and postorder traversals, we can use a recursive approach similar to the previous one for preorder and inorder traversals.\n# Intuition\nThe postorder traversal gives us the order in which nodes are visited in a "Left-Right-Root" manner, while the inorder traversal gives the order in "Left-Root-Right". By leveraging these properties, we can recursively construct the binary tree\n\n# Approach\nThe last element of the postorder traversal is the root of the tree.\nFind this root element in the inorder traversal; elements to the left of it belong to the left subtree, and elements to the right belong to the right subtree.\nRecursively repeat the process for the left and right subtrees using the respective segments of the inorder and postorder arrays.\n\n# Complexity\n- Time complexity:\nO(n^2)\nEach call to search takes O(n) time and it is called for each node. Therefore, in the worst case, the time complexity is O(n2)\n\n- Space complexity:\nO(n)\nThe space complexity is mainly due to the recursion stack, which can go up to the depth of the tree (in the worst case, the depth is n for a skewed tree)\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    int search(vector<int> inorder,int start,int end,int curr){\n        for(int i=start;i<=end;i++){\n            if(inorder[i]==curr){\n                return i;\n            }\n        }\n        return -1;\n    }\n    TreeNode* helper(vector<int>&inorder,vector<int>&postorder,int start,int end,int& idx){\n        if(start>end){\n            return nullptr;\n        }\n        int curr=postorder[idx];\n        idx--;\n        TreeNode* Node=new TreeNode(curr);\n        if(start==end){\n            return Node;\n        }\n        int pos=search(inorder,start,end,curr);\n        Node->right=helper(inorder,postorder,pos+1,end,idx);\n        Node->left=helper(inorder,postorder,start,pos-1,idx);\n        return Node;\n    }\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        int idx=inorder.size()-1;\n        TreeNode* root=helper(inorder,postorder,0,inorder.size()-1,idx);\n        return root;\n    }\n};\n```
['Array', 'Tree', 'Recursion', 'Binary Tree', 'C++']