Recursive (List Slicing & Indexes)


  • 0

    List Slicing:

    class Solution(object):
        def buildTree(self, inorder, postorder):
            """
            :type inorder: List[int]
            :type postorder: List[int]
            :rtype: TreeNode
            """
            if not inorder: return None
            # find head of current subtree
            currHead = postorder[len(postorder)-1]
            head = TreeNode(currHead)
            root = inorder.index(currHead)
            head.left = self.buildTree(inorder[:root],postorder[:root])
            head.right = self.buildTree(inorder[root+1:],postorder[root:len(postorder)-1])
            return head      
    

    Indexing:

    class Solution(object):
        def builder(self, inorder, postorder, iS, iE, pS, pE):
            if iS > iE: return None
            if iS == iE: return TreeNode(inorder[iS])
            currHead = postorder[pE]
            #print currHead
            head = TreeNode(currHead)
            root = None
            for i in range(iS, iE+1):
                if inorder[i] == currHead: 
                    root = i
                    break
            head.left = self.builder(inorder, postorder, iS, root-1, pS, pE-(iE-root)-1)
            head.right = self.builder(inorder, postorder, root+1, iE, root, pE-1)
            return head
            
        def buildTree(self, inorder, postorder):
            """
            :type inorder: List[int]
            :type postorder: List[int]
            :rtype: TreeNode
            """
            if not inorder: return None
            return self.builder(inorder, postorder, 0, len(inorder)-1, 0, len(inorder)-1)
    

Log in to reply
 

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