算法-二叉树-重建二叉树

重建二叉树：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

递归解法-python实现：

class Solution:
 # 返回构造的TreeNode根节点
     def reConstructBinaryTree(self, pre, tin): # write code here 
        if not pre or not tin: 
            return None 
        root = TreeNode(pre[0]) #先序遍历的第一位是根节点 
        index = tin.index(root.val)#找到中序遍历的根节点位置，切割左右子树 
        root.left = self.reConstructBinaryTree(pre[1:1+index], tin[:index]) 
        root.right = self.reConstructBinaryTree(pre[1+index:], tin[index+1:]) 
        return root