Fast and simple python solution (64ms, 9 lines)

  • 1


    1. use inddict, a dictionary of val:index in inorder, to reduce the runtime.

      Geting an item in a dictionary is O(1), but list.index() is O(n)
    2. use index pointers Lin, Rin for inorder instead of slicing to avoid 'Memory Limit Exceeded'

    **Solution 1, 9 lines, 64ms**
    def buildTree(self, preorder, inorder):
        def helper(Lin, Rin):
            if Lin < Rin:
                root = TreeNode(preorder.pop(0))
                rootind = inddict[root.val]
                root.left  = helper(Lin, rootind)
                root.right = helper(rootind+1, Rin)
                return root
        inddict = {val:i for i, val in enumerate(inorder)}
        return helper(0, len(inorder))

    Solution 2: same idea, just a variation of solution 1

    def buildTree(self, preorder, inorder):
        self.preorder, self.inorder = preorder, inorder
        self.inddict = {val:i for i, val in enumerate(inorder)}
        return self.helper(0, len(self.inorder))
    def helper(self, Lin, Rin):
        if Lin < Rin:
            root = TreeNode(self.preorder.pop(0))
            rootind = self.inddict[root.val]
            root.left  = self.helper(Lin, rootind)
            root.right = self.helper(rootind+1, Rin)
            return root

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.