题目：
给定两个数组，分别是前序遍历的结果和中序遍历的结果，返回该二叉树。样例如下：
解题思路：
已知前序遍历的第一个值一定是跟节点，在上例中，preorder的第一个值3作为根节点，再把inorder以3为间隔分开，左边为左子树，右边为右子树。而preorder中3之后跟的先是左子树的数值，再是右子树的数值，可以根据inorder得到的左子树和右子树的长度，将preorder除根节点以外，分为左子树的前序遍历和右子树的前序遍历结果。
从上一步可以得到左子树的前序遍历和中序遍历，以及右子树的前序遍历和中序遍历，再重复递归上述步骤即可。
代码：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def buildTree(self, preorder, inorder): """ :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """ def Iteration(preorder,inorder): if len(preorder)==0: return None if len(preorder)==1: return TreeNode(preorder[0]) root = TreeNode(preorder[0]) for i in range(len(inorder)): if inorder[i]==preorder[0]: break preorder0 = preorder[1:1+len(inorder[:i])] preorder1 = preorder[1+len(inorder[:i]):] root.left = Iteration(preorder0,inorder[:i]) root.right = Iteration(preorder1,inorder[i+1:]) return root return Iteration(preorder,inorder)