Discussion on Python Solution


  • 1
    Z

    One intuitive approach is by recursion. Code sample as follows:

    class Solution(object):
    	def buildTree(self, inorder, postorder):
    		"""
    		:type inorder: List[int]
    		:type postorder: List[int]
    		:rtype: TreeNode
    		"""
    		length = len(inorder)
    		# empty tree
    		if length == 0:
    			return None
    		val = postorder[-1]
    		root = TreeNode(val)
    		if length > 1:
    			cut  = inorder.index(val)
    			root.left = self.buildTree(inorder[:cut], postorder[:cut])
    			root.right = self.buildTree(inorder[cut+1:], postorder[cut:-1])
    		return root
    

    But if the tree is too deep, an error of "Memory Limit Exceeded" will pop up. To speed up the calculation, and to get around the restriction of recursion limit, the code has to using a stack to mimic the recursion function. Sample code as follow:

    class Solution(object):
    	def buildTree(self, inorder, postorder):
    		"""
    		:type inorder: List[int]
    		:type postorder: List[int]
    		:rtype: TreeNode
    		"""
    		length = len(inorder)
    		if length == 0:
    			return None
    		if length == 1:
    			return TreeNode(inorder[0])
    
    		root = TreeNode(None)
    		stack = [ (root, 0, length-1, length) ]
    		while stack:
    			# in_s (po_e): start (end) index of the "sub"-inorder (postorder)
    			node, in_s, po_e, size = stack.pop()
    			val = postorder[po_e]
    			node.val = val
    			idx = inorder.index(val)
    			# size of the left node
    			lsize = idx - in_s
    			# size of the right node
    			rsize = size - lsize - 1
    			if rsize == 0:
    				node.right = None
    			elif rsize == 1:
    				node.right = TreeNode(postorder[po_e - 1])
    			else:
    				node.right = TreeNode(None)
    				stack.append( (node.right, idx+1, po_e-1, rsize) )
    			if lsize == 0:
    				node.left = None
    			elif lsize == 1:
    				node.left = TreeNode(postorder[po_e - 1 - rsize])
    			else:
    				node.left = TreeNode(None)
    				stack.append( (node.left, in_s, po_e - 1 - rsize, lsize) )
    		return root

  • 0
    Y
    This post is deleted!

  • 1
    Y

    MLE happened because you create a new array every time you slice an array, which takes a lot more space.
    To avoid this problem, simply do a little change on your original code.

    class Solution(object):
        def buildTree(self, inorder, postorder):
            """
            :type inorder: List[int]
            :type postorder: List[int]
            :rtype: TreeNode
            """
            length = len(inorder)
            if length == 0:
                return None
            root = TreeNode(postorder[-1])
            m = inorder.index(postorder[-1])
            postorder.pop()
            root.right = self.buildTree(inorder[m+1: length], postorder)
            root.left = self.buildTree(inorder[0: m], postorder)
            return root
    

Log in to reply
 

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