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

Only Solution 3 could pass the OJ, but theoretically they should all work ...

**Solution 1 - clean and easy to understand, but Memory Limit Exceeded ...**

```
# 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[0]
root = TreeNode(rootValue)
inorderIndex = inorder.index(rootValue)
root.left = self.buildTree(preorder[1:inorderIndex+1], inorder[:inorderIndex])
root.right = self.buildTree(preorder[inorderIndex+1:], inorder[inorderIndex+1:])
return root
```

**Solution 2 - Same as solution one, but pass index instead of doing list slicing (and thus reduce the memory usage)**

```
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, preorderStart = 0, preorderEnd = None, inorderStart = 0, inorderEnd = None):
if preorderEnd is None:
preorderEnd = len(preorder) - 1
if inorderEnd is None:
inorderEnd = len(inorder) - 1
if preorderStart > len(preorder) - 1 or inorderStart > inorderEnd:
return None
rootValue = preorder[preorderStart]
root = TreeNode(rootValue)
inorderIndex = inorder.index(rootValue)
root.left = self.buildTree(preorder, inorder, preorderStart+1, inorderIndex, inorderStart, inorderIndex-1)
root.right = self.buildTree(preorder, inorder, preorderStart+inorderIndex+1-inorderStart, preorderEnd, inorderIndex+1, inorderEnd)
return root
```

**Solution 3 - Based on Solution 1, we don't necessary need to slice the preorder array, when we are done with the left tree, the left half of the preorder array should already be empty**

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