O(n) python


  • 0
    D
    # get element -> index dict as cache
    def getD(arr):
        d = {}
        for i in range(len(arr)):
            d[arr[i]] = i
        return d
    
    class Solution(object):
        def buildTree(self, preorder, inorder):
            self.preorder = preorder     
            self.d = getD(inorder)
            n = len(preorder)
            return self.recurse(0, n-1, 0, n-1)
        
        def recurse(self, i1, j1, i2, j2):
            if i1 > j1:
                return None
            val = self.preorder[i1] # get the head of current subtree
            head = TreeNode(val) # create a node
            p = self.d[val] # find out the corresponding node in inorder traversal
            leftlen = p-i2 # calculate the length of the left part
            head.left = self.recurse(i1+1, i1+leftlen, i2, p-1) # recurse on left
            head.right = self.recurse(i1+leftlen+1, j1, p+1, j2) # right
            return head
    

Log in to reply
 

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