剑指offer-7.重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题思路:

1.前序遍历序列的第一个就是根节点

2.找到根节点在对应中序遍历节点中的位置，中序遍历中根节点前面的序列就是左子树的中序遍历，同理，后面的部分就是右子树的中序遍历

3.得到左右子树的中序遍历，按照他们中序遍历序列的个数可以求出对应的前序遍历

4.不断重复这个过程，可以采用递归的方法去实现

 1 class Solution:
 2     # 返回构造的TreeNode根节点
 3     def reConstructBinaryTree(self, pre, tin):
 4         # write code here
 5         if set(pre)!=set(tin):
 6             return None
 7         if not pre or not tin:
 8             return None
 9         root=TreeNode(pre[0])
10         p=tin.index(pre[0])
11         root.left=self.reConstructBinaryTree(pre[1:p+1],tin[:p])
12         root.right=self.reConstructBinaryTree(pre[p+1:],tin[p+1:])
13         return root