# Discussion on Python Solution

• 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``````

• This post is deleted!

• 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
``````

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