# Share my recursive and iterative Python solutions, O(N) ~70 ms

• Both solutions use dictionary to create mapping between value and index of in-order traversal.

Recursive one: use deque for efficient popleft()

``````from collections import deque
class Solution:
# @param {integer[]} preorder
# @param {integer[]} inorder
# @return {TreeNode}
def buildTree(self, preorder, inorder):
def _buildTreeHelper(preorder, inorder, start, end, inorderMapping):
# escape condition
if start > end:
return None

# root is the first one in pre-order
root = TreeNode(preorder.popleft())
# get root's index in in-order
index = inorderMapping[root.val]
# build left / right sub-trees
root.left = _buildTreeHelper(preorder, inorder, start, index-1, inorderMapping)
root.right = _buildTreeHelper(preorder, inorder, index+1, end, inorderMapping)
return root

# generate mapping from value to index
inorderMapping = {inorder[index] : index for index in range(len(inorder))}
preorder = deque(preorder)
return _buildTreeHelper(preorder, inorder, 0, len(inorder)-1, inorderMapping)
``````

Iterative one: I could use deque too. Instead, I just reverse inorder and use pop() instead of pop(0)
Use stack to store start / end index of inorder, as well as parent and indicator of left child or right child.

``````class Solution:
# @param {integer[]} preorder
# @param {integer[]} inorder
# @return {TreeNode}
def buildTree(self, preorder, inorder):
dummy = TreeNode(0)
if inorder:
# generate mapping from value to index
inorderMapping = {inorder[index] : index for index in range(len(inorder))}
preorder = preorder[::-1]
stack = [(0, len(inorder)-1, dummy, True)]
while stack:
start, end, parent, left = stack.pop()
node = TreeNode(preorder.pop())
if left:
parent.left = node
else:
parent.right = node
index = inorderMapping[node.val]
if index < end:
stack.append((index+1, end, node, False))
if index > start:
stack.append((start, index-1, node, True))

return dummy.left``````

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