🔥Easy Solutions in Java 📝, Python 🐍, and C++ 🖥️🧐Look at once 💻
Intuition\n Describe your first thoughts on how to solve this problem. \nTo construct a binary tree from inorder and postorder traversal arrays, we first need t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo construct a binary tree from inorder and postorder traversal arrays, we first need to understand what each of these traversals represents.\nInorder traversal visits the nodes in ascending order of their values, i.e., left child, parent, and right child. On the other hand, postorder traversal visits the nodes in the order left child, right child, and parent.\nKnowing this, we can say that the last element in the postorder array is the root node, and its index in the inorder array divides the tree into left and right subtrees. We can recursively apply this logic to construct the entire binary tree.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Start with the last element of the postorder array as the root node.\n2. Find the index of the root node in the inorder array.\n3. Divide the inorder array into left and right subtrees based on the index of the root node.\n4. Divide the postorder array into left and right subtrees based on the number of elements\nin the left and right subtrees of the inorder array.\n5. Recursively construct the left and right subtrees.\n\n\n\n\n\n# Complexity\n- Time complexity:\nThe time complexity of this algorithm is O(n), where n is the number of nodes in the tree. We visit each node only once.\n\n- Space complexity:\nThe space complexity of this algorithm is O(n). We create a hashmap to store the indices of the inorder traversal, which takes O(n) space. Additionally, the recursive call stack can go up to O(n) in the worst case if the binary tree is skewed.\n\n\n\n\n![image.png](https://assets.leetcode.com/users/images/b427e686-2e5d-469a-8e7a-db5140022a6b_1677715904.0948765.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A\n```\n# Code\n``` Java []\nlass Solution {\n    public TreeNode buildTree(int[] inorder, int[] postorder) {\n        // Call the recursive function with full arrays and return the result\n        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);\n    }\n    \n    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {\n        // Base case\n        if (inStart > inEnd || postStart > postEnd) {\n            return null;\n        }\n        \n        // Find the root node from the last element of postorder traversal\n        int rootVal = postorder[postEnd];\n        TreeNode root = new TreeNode(rootVal);\n        \n        // Find the index of the root node in inorder traversal\n        int rootIndex = 0;\n        for (int i = inStart; i <= inEnd; i++) {\n            if (inorder[i] == rootVal) {\n                rootIndex = i;\n                break;\n            }\n        }\n        \n        // Recursively build the left and right subtrees\n        int leftSize = rootIndex - inStart;\n        int rightSize = inEnd - rootIndex;\n        root.left = buildTree(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);\n        root.right = buildTree(inorder, rootIndex + 1, inEnd, postorder, postEnd - rightSize, postEnd - 1);\n        \n        return root;\n    }\n}\n\n\n```\n```Python []\nclass Solution(object):\n    def buildTree(self, inorder, postorder):\n        """\n        :type inorder: List[int]\n        :type postorder: List[int]\n        :rtype: TreeNode\n        """\n        # Base case\n        if not inorder:\n            return None\n        \n        # The last element of postorder list is the root\n        root_val = postorder.pop()\n        root = TreeNode(root_val)\n        \n        # Find the position of the root in the inorder list\n        inorder_index = inorder.index(root_val)\n        \n        # Recursively build the left and right subtrees\n        root.right = self.buildTree(inorder[inorder_index+1:], postorder)\n        root.left = self.buildTree(inorder[:inorder_index], postorder)\n        \n        return root\n\n```\n```C++ []\nclass Solution {\npublic:\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        unordered_map<int, int> index;\n        for (int i = 0; i < inorder.size(); i++) {\n            index[inorder[i]] = i;\n        }\n        return buildTreeHelper(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1, index);\n    }\n    \n    TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder, int inorderStart, int inorderEnd, int postorderStart, int postorderEnd, unordered_map<int, int>& index) {\n        if (inorderStart > inorderEnd || postorderStart > postorderEnd) {\n            return nullptr;\n        }\n        int rootVal = postorder[postorderEnd];\n        TreeNode* root = new TreeNode(rootVal);\n        int inorderRootIndex = index[rootVal];\n        int leftSubtreeSize = inorderRootIndex - inorderStart;\n        root->left = buildTreeHelper(inorder, postorder, inorderStart, inorderRootIndex - 1, postorderStart, postorderStart + leftSubtreeSize - 1, index);\n        root->right = buildTreeHelper(inorder, postorder, inorderRootIndex + 1, inorderEnd, postorderStart + leftSubtreeSize, postorderEnd - 1, index);\n        return root;\n    }\n};\n\n\n```\n# Please Comment\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution comment below if you like it.\uD83D\uDE0A\n```
['Divide and Conquer', 'Tree', 'Python', 'C++', 'Java']