What's wrong with my python code , result is MLE


  • 0
    class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder:return
        curr=TreeNode(preorder[0])
        index=inorder.index(preorder[0])
        curr.left=self.buildTree(preorder[1:index+1],inorder[:index])
        curr.right=self.buildTree(preorder[index+1:],inorder[index+1:])
        return curr

  • 0
    L

    You made two new lists as parameters in each recursive call, which required a lot of memory. You can try to pass in the original lists together with the correct indices.


  • 0

    sorry, I am confused that I used indices such as preorder[1:index+1],but u said I made two new lists, I didn't get it! can u explain more clearly, THx!


  • 0
    L

    for example, in curr.left=self.buildTree(preorder[1:index+1],inorder[:index]), you made two lists preorder[1:index+1] and inorder[:index]


  • 0

    I think they're the indices of preorder[1:index+1] and inorder[:index]. Are they not?then how to get the indices?THx for ur help again!


  • 0
    L

    I was using a helper function like

    def buildTreeHelper(self, preorder, i, j, inorder, m, n):
    

    where preorder[i:j] would be equivalent to preorder[1:index+1] in your solution and similarly inorder[m:n] would be equivalent to inorder[:index]. In this way, each recursive call uses the original lists and takes the indices as the boundaries.The trick part is to figure out the indices that need to be passed in.

    Let me know if you have further questions.


  • 0

    oh,yeah, I got it! thx very much!


  • 0
    L

    no problem :)


Log in to reply
 

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