Python -- Arriving at an O(N) solution
Initial answer/thought process:\n\nWell -- the first thing I notice with the provided example (inorder: [9,3,15,20,7], postorder: [9,15,7,20,3]) is that the roo
Initial answer/thought process:\n\nWell -- the first thing I notice with the provided example (inorder: [9,3,15,20,7], postorder: [9,15,7,20,3]) is that the root is the last value in postorder. Next, we can see that all the values to the left of this root (3) in inorder are in the root\'s left subtree, and all of the values to the right of the root in order are in the root\'s right subtree. So, we get some intuition that a recursive approach here might work.\n\nLet\'s pop off the root in postorder -- the last element -- and then get its left and right subtrees:\n\nnew postorder: [9, 15, 7, 20]\nleft inorder: [9]\nright inorder: [15, 20, 7]\n\nSo we can make the root, and now we need to handle making the left subtree and the right subtree with these values. Well, what I noticed is that the root of the right subtree is now the last value in the new postorder -- aha! The recursive approach becomes clear. We need to recursively repeat this process with the right subtree until there\'s nothing else in this right subtree, and then the only nodes left in the trimmed postorders are in the left subtree, so we can then handle that case:\n\n\n    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n        if not (inorder and postorder):\n            return None\n        r_val = postorder.pop()\n        left = inorder[:inorder.index(r_val)]\n        right = inorder[inorder.index(r_val) + 1:]\n        root = TreeNode(r_val)\n        root.right = self.buildTree(right, postorder)\n        root.left = self.buildTree(left, postorder)\n        return root\n\nTime: 39th percentile\nSpace: 39th percentile\n\nMaking sublists and using the index function is a bit suspicious/slow in time and space. Annoyingly, this means we\'ll have to make the "niceness" of this solution a little harder to follow for the sake of saving time and space. First, we don\'t want to use O(N) functions in recursive calls, so we should spot these inefficiencies and think of how to shorten them to O(1) time. The one that sticks out to me here is using index, since that\'s a linear search. Instead, we can just make a hashmap that maps values to their index in inorder. This of course is still O(N), but we only need to do this once so that recursive calls can just use this map to find the appropriate index in O(1) time. Next, instead of making sublists, we can just store the indices for the bounds on the array we\'d normally shrink. Essentially we\'re virtually shrinking the array. The result is a better solution in terms of time and space, but it\'s a bit more confusing to understand:\n\n    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n        m = {}\n        for idx, r in enumerate(inorder):\n            m[r] = idx\n        def help(left, right):\n            if not (postorder and left <= right):\n                return None\n            r_val = postorder.pop()\n            idx = m[r_val]\n            root = TreeNode(r_val)\n            root.right = help(idx + 1, right)\n            root.left = help(left, idx - 1)\n            return root\n        return help(0, len(postorder) - 1)\n\nTime: 94th percentile\nSpace: 90th percentile\n\nTough problem to get an efficient solution to.
['Python']