Very very similar with last problem.
Solution:
# T:O(n) S:O(n) class Solution: # @param inorder, a list of integers # @param postorder, a list of integers # @return a tree node def buildTree(self, inorder, postorder): lookup = {} for i, num in enumerate(inorder): lookup[num] = i return self.buildTreeRecu(lookup, postorder, inorder, len(postorder), 0, len(inorder)) def buildTreeRecu(self, lookup, postorder, inorder, post_end, in_start, in_end): if in_start == in_end: return None node = TreeNode(postorder[post_end - 1]) i = lookup[postorder[post_end - 1]] node.left = self.buildTreeRecu(lookup, postorder, inorder, post_end - 1 - (in_end - i - 1), in_start, i) node.right = self.buildTreeRecu(lookup, postorder, inorder, post_end - 1, i + 1, in_end) return nodeRun Time: 88 ms
No comments:
Post a Comment