Day 75 || Divide and Conquer + Hash Table || Easiest Beginner Friendly Sol
NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.\n\n# Intuitio
**NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Intuition of this Problem :\nThe problem is to construct a binary tree from inorder and postorder traversals of the tree. The inorder traversal gives the order of nodes in the left subtree, root, and right subtree, while the postorder traversal gives the order of nodes in the left subtree, right subtree, and root.\n\n**The intuition behind the algorithm is to start by identifying the root of the binary tree from the last element of the postorder traversal. Then, we can use the root to divide the inorder traversal into left and right subtrees. We can then recursively apply the same process to the left and right subtrees to construct the entire binary tree.**\n\nTo do this efficiently, we can use a hash map to store the indices of elements in the inorder traversal. This allows us to quickly find the position of the root in the inorder traversal and divide the traversal into left and right subtrees.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach for this Problem :\n1. Create a function called buildTree that takes in two vectors, inorder and postorder, and returns a pointer to the root of the resulting binary tree.\n2. Initialize an integer variable postorderIndex to postorder.size() - 1. This variable will be used to traverse the postorder vector in reverse order.\n3. Initialize an empty unordered map called inorderIndexUmp. This map will be used to quickly look up the index of a value in the inorder vector.\n4. Loop through the inorder vector and insert each value and its index into the inorderIndexUmp map.\n5. Call a recursive helper function called buildTreeHelper with parameters postorder, 0, and postorder.size() - 1. This function will return the root of the binary tree.\n6. In the buildTreeHelper function, if left is greater than right, return nullptr.\n7. Get the root value from the postorder vector using the postorderIndex variable, and decrement postorderIndex.\n8. Create a new TreeNode with the root value and assign it to a pointer variable called root.\n9. Get the index of the root value in the inorder vector from the inorderIndexUmp map, and assign it to an integer variable called inorderPivotIndex.\n10. Recursively call buildTreeHelper with parameters postorder, inorderPivotIndex + 1, and right. Assign the result to root -> right.\n11. Recursively call buildTreeHelper with parameters postorder, left, and inorderPivotIndex - 1. Assign the result to root -> left.\n12. Return root.\n<!-- Describe your approach to solving the problem. -->\n\n# Code :\n```C++ []\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 postorderIndex;\n    unordered_map<int, int> inorderIndexUmp;\n\n    TreeNode* buildTreeHelper(vector<int>& postorder, int left, int right) {\n        if (left > right)\n            return nullptr;\n        int rootValue = postorder[postorderIndex--];\n        TreeNode* root = new TreeNode(rootValue);\n        int inorderPivotIndex = inorderIndexUmp[rootValue];\n        //think about it...why I took root -> right first then root -> left ?\n        root -> right = buildTreeHelper(postorder, inorderPivotIndex + 1, right);\n        root -> left = buildTreeHelper(postorder, left, inorderPivotIndex - 1);\n        return root;\n    }\n\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        postorderIndex = postorder.size() - 1;\n        for (int i = 0; i < inorder.size(); i++) {\n            inorderIndexUmp[inorder[i]] = i;\n        }\n        return buildTreeHelper(postorder, 0, postorder.size() - 1);\n    }\n};\n```\n```Java []\nclass 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    int postorderIndex;\n    Map<Integer, Integer> inorderIndexUmp;\n\n    public TreeNode buildTree(int[] inorder, int[] postorder) {\n        postorderIndex = postorder.length - 1;\n        inorderIndexUmp = new HashMap<Integer, Integer>();\n        for (int i = 0; i < inorder.length; i++) {\n            inorderIndexUmp.put(inorder[i], i);\n        }\n        return buildTreeHelper(postorder, 0, postorder.length - 1);\n    }\n\n    private TreeNode buildTreeHelper(int[] postorder, int left, int right) {\n        if (left > right)\n            return null;\n        int rootValue = postorder[postorderIndex--];\n        TreeNode root = new TreeNode(rootValue);\n        int inorderPivotIndex = inorderIndexUmp.get(rootValue);\n        root.right = buildTreeHelper(postorder, inorderPivotIndex + 1, right);\n        root.left = buildTreeHelper(postorder, left, inorderPivotIndex - 1);\n        return root;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def buildTreeHelper(self, postorder: List[int], left: int, right: int) -> TreeNode:\n        if left > right:\n            return None\n        root_value = postorder[self.postorder_index]\n        self.postorder_index -= 1\n        root = TreeNode(root_value)\n        inorder_pivot_index = self.inorder_index_map[root_value]\n        root.right = self.buildTreeHelper(postorder, inorder_pivot_index + 1, right)\n        root.left = self.buildTreeHelper(postorder, left, inorder_pivot_index - 1)\n        return root\n\n    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n        self.postorder_index = len(postorder) - 1\n        self.inorder_index_map = {val: i for i, val in enumerate(inorder)}\n        return self.buildTreeHelper(postorder, 0, len(postorder) - 1)\n\n```\n\n# Time Complexity and Space Complexity:\n- Time complexity : **O(n)**, The buildTreeHelper() function is called for each node in the tree exactly once, and the time complexity of each call is O(1). Therefore, the overall time complexity of the algorithm is O(n), where n is the number of nodes in the tree.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity : **O(n)**, where n is the number of nodes in the tree. This is because we are creating a new TreeNode object for each node in the tree, and we are also using an unordered_map to store the indices of the nodes in the inorder traversal. Additionally, the recursive calls to buildTreeHelper() create a call stack of size O(n) in the worst case, where n is the number of nodes in the tree.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n**YOU CAN ALSO TRY BELOW PROBLWM WHICH IS SIMILAR TO THIS PROBLEM**\n105. Construct Binary Tree from Preorder and Inorder Traversal\n**SOLUTION :**\nhttps://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/3303059/divide-and-conquer-hash-table-easiest-beginner-friendly-sol/
['Hash Table', 'Divide and Conquer', 'C++', 'Java', 'Python3']