题目分析：
根据一棵树的前序遍历与中序遍历构造二叉树。注意：你可以假设树中没有重复的元素。 例如，给出：前序遍历 preorder = [3,9,20,15,7]、中序遍历 inorder = [9,3,15,20,7]。返回如下的二叉树： 解题思路：
这一题我们首先需要找到构造二叉树的规律： preorder: 3 9 20 15 7
inorder: 9 3 15 20 7
找到第一个根节点（前序遍历的第一个元素）
3 9 20 15 7 9 3 15 20 7
那么中序遍历中3左边的就是左子树，3右边的就是右子树 那么现在产生了两组前序与中序， 左树的前序与中序是（9）（9） 右树的前序与中序是（20 15 7）（15 20 7）
9 20 15 7 9 15 20 7
左树递归执行第一步，已经没法再添加了，就设置None 右树递归执行第一步，左边添加15，右边添加7 15和7的情况与第三步类似，添加None提交代码1：（简洁递归，时间复杂度O(N2)，Runtime: 188 ms, faster than 45.52% ）
class Solution: def buildTree(self, preorder: 'List[int]', inorder: 'List[int]') -> TreeNode: if not preorder: return None root = TreeNode(preorder[0]) index = inorder.index(preorder[0]) root.left = self.buildTree(preorder[1 : index + 1],inorder[: index]) root.right = self.buildTree(preorder[index + 1 :],inorder[index+1 :]) return root提交代码2：（使用字典不必每次切割数组的递归，切片的时间复杂度是O(N)，使时间复杂度下降到O(N)，Runtime: 44 ms, faster than 99.69% ）
class Solution: def buildTree(self, preorder, inorder): map_inorder = {} for i, val in enumerate(inorder): map_inorder[val] = i def recur(low, high): if low > high: return None root = TreeNode(preorder.pop(0)) index = map_inorder[root.val] root.left = recur(low, index - 1) root.right = recur(index + 1, high) return root return recur(0, len(inorder)-1)参考博客
最近遇到了一些烦心事，有种深深的无力感，不能掌控自己的命运前途真是令人感到不安，坚持吧，乐观点，一切都是云烟
