Python with cache that beats 99% submissions

  • 0
    class Solution(object):
        def buildTree(self, preorder, inorder):
            :type preorder: List[int]
            :type inorder: List[int]
            :rtype: TreeNode
            if not preorder:
                return None
            self.preorder = preorder
            self.inorder = inorder
            self.inorder_map = dict([(n,i) for (i,n) in enumerate(inorder)])
            return self._build(0, len(preorder), 0, len(inorder))
        def _build(self, p_start, p_end, i_start, i_end):
            if p_start >= p_end or i_start >= i_end:
                return None
            curr = TreeNode(self.preorder[p_start])
            inorder_i = self.inorder_map[self.preorder[p_start]]
            diff = inorder_i - i_start
            curr.left = self._build(1+p_start, diff+1+p_start, i_start, inorder_i)
            curr.right = self._build(diff+1+p_start, p_end, inorder_i+1, i_end)
            return curr

    This method assumes no duplicate.

Log in to reply

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