Python recursion solution, AC


  • 0
    D

    idea:

    inorder: DGBAECF

    postorder: GDBEFCA

    f(inorder, postorder, 7)

    i--

    root = A

    root.right = f('ECF', postorder(unchanged), 6)

    root.left = f('DGB', postorder(unchanged), x(every time in function i--))

    class Solution:
    # @param inorder, a list of integers
    # @param postorder, a list of integers
    # @return a tree node
    def buildTree(self, inorder, postorder):
        if len(inorder) == 0 or len(postorder) == 0:
            return None
        root = self.create(inorder, postorder, [len(postorder)])
        return root
    
    def create(self, inorder, postorder, ilist):
        #because ptr* in not available in python, so i use list instead, if u have a better idea, tell me
        ilist[0] -= 1
        i = ilist[0]
        #find current root
        cur = postorder[i]
        #root
        root = TreeNode(cur)
        #find root in inorder, we assume it can be find
        split_index = inorder.index(cur)
        #root.right
        if split_index + 1 < len(inorder):
            root.right = self.create(inorder[split_index+1:], postorder, ilist)
        else:
            root.right = None
        #root.left
        if split_index > 0:
            root.left = self.create(inorder[:split_index], postorder, ilist)
        else:
            root.left = None
        #return
        return root

  • 4
    L

    Since Python has a property that you can use a list as a queue or a stack, you can just pop out the last element in the postorder. Although I don't think it's a good idea to use an array as a stack in an interview, it does simplify the code :P

    class Solution:
        # @param inorder, a list of integers
        # @param postorder, a list of integers
        # @return a tree node
        def buildTree(self, inorder, postorder):
            if len(inorder) == 0:
                return None
            cur = postorder.pop(-1)
            root = TreeNode(cur)
            for i in xrange(len(inorder)):
                if inorder[i] == cur:
                    root.right = self.buildTree(inorder[i+1:], postorder)
                    root.left = self.buildTree(inorder[:i], postorder)
                    break
            return root

  • 0
    L

    just slice the list

    def buildTree(self, inorder, postorder):
            if len(postorder) == 0 :
                return None
            else:
                node = TreeNode(postorder[-1])
                i = inorder.index(postorder[-1])
                node.left = self.buildTree(inorder[0:i],postorder[0:i])
                node.right = self.buildTree(inorder[i+1:],postorder[i:-1])
                return node

  • 0
    B

    your code get the memory limit error


  • 0
    P

    Yes. Me too.


Log in to reply
 

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