# An easy Python solution

• The idea is to find the root first, then recursively build each left and right subtree

``````# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param num, a list of integers
# @return a tree node
# 12:37
def sortedArrayToBST(self, num):
if not num:
return None

mid = len(num) // 2

root = TreeNode(num[mid])
root.left = self.sortedArrayToBST(num[:mid])
root.right = self.sortedArrayToBST(num[mid+1:])

return root``````

• Hello, maybe this is not perfect place to ask this question. But I am very curious whether we are allowed use a copy of lists in these recursive functions in the interview (num[:mid] and num[mid+1:] are actually creating extra sublists). It works for this problem well but for problems like ConstructBinaryTreeFromPreorderAndInoderTraversal, when I used similar method which is very straightforwad , it works locally but OJ gives memory limit exceed. Later I solved it by dealing with indexes instead of passing copy of lists(300+ms) and improved it with the help of hash table(70+ms) but it took me long time. I hope to use the first solution if possible since we don't have much time.

``````class Solution:
# @param {integer[]} preorder
# @param {integer[]} inorder
# @return {TreeNode}
def buildTree(self, preorder, inorder):
if not preorder:
return
root = TreeNode(preorder[0])
self._buildTree(preorder, inorder, root)
return root

def _buildTree(self, preorder, inorder, root):
if not preorder:
return
for i, num in enumerate(inorder):
if root.val == num:
break
if i != 0:
root.left = TreeNode(preorder[1])
self._buildTree(preorder[1:i+1], inorder[:i], root.left)
if i != len(preorder) - 1:
root.right = TreeNode(preorder[i+1])
self._buildTree(preorder[i+1:], inorder[i+1:], root.right)

class Solution:
# @param {integer[]} preorder
# @param {integer[]} inorder
# @return {TreeNode}
def buildTree(self, preorder, inorder):
if not preorder:
return
return self._buildTree(preorder, inorder, 0, len(preorder) - 1, 0, len(inorder) - 1)

def _buildTree(self, preorder, inorder, pre_start, pre_end, in_start, in_end):
if pre_start > pre_end:
return
root = TreeNode(preorder[pre_start])
for i in range(in_start, in_end + 1):
if root.val == inorder[i]:
break
if in_start != i:
root.left = self._buildTree(preorder, inorder, pre_start + 1, pre_start + i - in_start, in_start, i - 1)
if in_end != i:
root.right = self._buildTree(preorder, inorder, pre_start + i - in_start + 1, pre_end, i + 1, in_end)
return root

class Solution:
# @param {integer[]} preorder
# @param {integer[]} inorder
# @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
root_val = self.preorder[self.preorder_index]
node = TreeNode(root_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``````

• You don't necessary need to slice and make a copy of the preOrder

``````# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param preorder, a list of integers
# @param inorder, a list of integers
# @return a tree node
# 1:59
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None

rootValue = preorder.pop(0)
root = TreeNode(rootValue)
inorderIndex = inorder.index(rootValue)

root.left = self.buildTree(preorder, inorder[:inorderIndex])
root.right = self.buildTree(preorder, inorder[inorderIndex+1:])

return root``````

• Are you not creating new lists by calling inorder[:inorderIndex] and inorder[inorderIndex+1:]? It takes around 300ms. However, I think I will use this solution in a interview since it's easy to write. Btw, I tried to do it in your way and ended up with the following solution similar to yours but slicing preorder instead of inorder :)

``````def buildTree(self, preorder, inorder):
if not preorder:
return
val = preorder[0]
root = TreeNode(val)
i = inorder.index(val)
inorder.remove(val)
root.left = self.buildTree(preorder[1:i+1], inorder)
root.right = self.buildTree(preorder[i+1:], inorder)
return root``````

• If you try [0,1] you will return [1,0] rather than the expected [0,null,1], although the answer is also accepted.
So I would suggest to set mid = len(nums)//2 if len(nums)%2 != 0 else len(nums)//2 - 1

• In my opinion, to meet the problem's requirement, we just need to change "mid = len(nums) // 2" to "mid = (len(nums) - 1) // 2"

• @Google my solution as well. But when I test
[1, 2, 3, 4, 5, 6, 7, 12, 24, 125]
it doesn't give the same result as expected. And this is just a random list I typed to replace the empty list template.

• @swengzju Thank you for letting me know that the answer would be accepted. I wrote the same codes and I did customized testing, I was scared by the result. I literally don't know how to general that "null" in Python.

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