# O(n) simple python solution

• ``````class Solution:
# @param {integer[]} preorder
# @param {integer[]} inorder
# @return {TreeNode}
def buildTree(self, preorder, inorder):
if not preorder:
return None

m = {}
for i in range(0, len(inorder)):
m[inorder[i]] = i
return self.construct_bst_help(preorder, 0, len(preorder), m, [0])

def construct_bst_help(self, preorder, start, end, m, curr):
if start == end:
return None
if start == end - 1:
node = TreeNode(preorder[curr[0]])
curr[0] += 1
return node

node = TreeNode(preorder[curr[0]])
curr[0] += 1

i = m[node.val]
node.left = self.construct_bst_help(preorder, start, i, m, curr)
node.right = self.construct_bst_help(preorder, i + 1, end, m, curr)
return node``````

• It is very nice! I came up with a solution similar to the following link by checking the start and end positions of each sub-list, which got many votes, but it only has 300+ms performance in python. I wanted to improve that with dictionary somehow, but I saw this first, which saved me a lot time. Thumbs up for this solution, thanks!

https://leetcode.com/discuss/18101/sharing-my-straightforward-recursive-solution

• I just want to make it easier to read with fewer parameters. Hopefully it can help someone.

``````class Solution:
# @param {integer[]} inorder
# @param {integer[]} postorder
# @return {TreeNode}
def __init__(self):
self.preorder = []
self.preorder_index = 0
self.inorder_indexes = {}

def buildTree(self, preorder, inorder):
if not preorder:
return
self.preorder = preorder
for i, num in enumerate(inorder):
self.inorder_indexes[num] = i
return self._buildTree(0, len(preorder) - 1)

def _buildTree(self, start, end):
if self.preorder_index == len(self.preorder) or start > end:
return
node_val = self.preorder[self.preorder_index]
node = TreeNode(node_val)
self.preorder_index += 1
if start == end:
return node
mid = self.inorder_indexes[root_val]
node.left = self._buildTree(start, mid - 1)
node.right = self._buildTree(mid + 1, end)
return node``````

• Nice solution, while the code can be shorten a little bit:

``````# O(n)
def buildTree(self, preorder, inorder):
if not preorder:
return None
dic = {}
for i, val in enumerate(inorder):
dic[val] = i
# the root node index in preorder array
self.indPre = 0
return self.help_fun(preorder, 0, len(preorder)-1, dic)

def help_fun(self, preorder, start, end, dic):
if start > end or self.indPre == len(preorder):
return None
root = TreeNode(preorder[self.indPre])
self.indPre += 1
index = dic[root.val]
root.left = self.help_fun(preorder, start, index-1, dic)
root.right = self.help_fun(preorder, index+1, end, dic)
return root``````

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