输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
限制：
0 <= 节点个数 <= 5000
先说下吧，这道题，，背过吧，实际开发没什么意义。工作就慢慢就理解了。
首先说下原理，先序遍历的第一个节点是根节点，这道题说不存在重复的元素，从而中序遍历的这个节点就可以将中序遍历结果分成两个子树，先序遍历的结果中去掉子节点，然后可以根据中序遍历拆成的两个子树的节点，分别再次确定下两个子树的根节点，像这种一步一步递归下去就可以确定每个节点的位置。从这种递归和区间分治的思想就可以看出，这道题的解法就这样，但是节点数量是大于1000的，所以递归最好不要用。改成迭代就好。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
def buildTree_recur(preorder_left,preorder_right,inorder_left,inorder_right):
if preorder_left>preorder_right:
return None
preorder_root_index = preorder_left
inorder_root_index = index[preorder[preorder_root_index]]
root = TreeNode(preorder[preorder_root_index])
size_left = inorder_root_index - inorder_left
root.left = buildTree_recur(preorder_left+1,preorder_left+size_left,inorder_left,inorder_root_index-1)
root.right = buildTree_recur(preorder_left+1+size_left,preorder_right,inorder_root_index+1,inorder_right)
return root
n = len(preorder)
index = {element:i for i,element in enumerate(inorder)}
return buildTree_recur(0,n-1,0,n-1)这里刚好可以复习下简单哈希表的创建
有空补下迭代的解法：