Neat O(n) space Python solution beats 97%

  • 1

    Idea: Use pre-order list to locate root node in inorder list recursively.
    Use dictionary to speed up lookup.

    class Solution(object):
        def buildTree(self, preorder, inorder):
            :type preorder: List[int]
            :type inorder: List[int]
            :rtype: TreeNode
            self.preindex = 0
            ind = {v:i for i, v in enumerate(inorder)}
            head = self.dc(0, len(preorder) - 1, preorder, inorder, ind)
            return head
        def dc(self, start, end, preorder, inorder, ind):
            if start <= end:
                mid = ind[preorder[self.preindex]]
                self.preindex += 1
                root = TreeNode(inorder[mid])
                root.left = self.dc(start, mid - 1, preorder, inorder, ind)
                root.right = self.dc(mid + 1, end, preorder, inorder, ind)
                return root

Log in to reply

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