题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{ 1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路一：
首先，前序遍历遵循 中左右的遍历顺序 故第一个元素必定是根节点，即 ‘1’
中序遍历遵循左中右的遍历顺序，故首先需要找到‘1’在中序中的位置 4 (此时i = 3)
此时可以得出，中序列的{4,7,2}都属于左子树，{5,3,8,6}属于右子树
同样可以得知，前序中根节点为【0】,左子树为[1:3]，右子树为【4：len(前序)-1】
此时只需将左子树序列与右子树序列分开进行递归，即可构建出完整的二叉树
即 root.left = self.reConstructBinaryTree([2,4,7], [4,7,2])
root.right = self.reConstructBinaryTree([3,5,6,8], [5,3,8,6])
class Solution:def reConstructBinaryTree(self, pre, tin):if len(pre) == 0 or len(tin) == 0: #如果中序或前序为空return Noneif len(pre) == 1 or len(tin) == 1: #如果前序或中序只有一个元素return TreeNode(pre[0])root = TreeNode(pre[0]) #创建树，根节点=前序的第一个数for i in range(len(tin)): #遍历中序列表if tin[i] == root.val: #找出中序列表，根节点的位置root.left = self.reConstructBinaryTree(pre[1:i + 1], tin[:i]) #中序列中，根节点的左子树的元素都在其左边#前序列中，第一个是根节点，从第二个开始往后推i位 都是左子树root.right = self.reConstructBinaryTree(pre[i + 1:], tin[i + 1:])#中序列中，根节点的右子树的元素都在其右边#前序列中，左子树之后的都为右子树return root这个解法优雅而巧妙，越看越舒服。也许这就是AC的美妙之处吧