# Python recursion solution, AC

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

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

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

• your code get the memory limit error

• Yes. Me too.

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