04_重建二叉树【python】

1.问题描述

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

2.思路

首先，提到二叉树条件反射应该是递归
1.先序遍历的第一个节点一定是根节点
2.中序遍历，根节点前面的是左子树，后面的是右子树
3.用数学归纳法的思想，假设现在是最后一步，左子树和右子树都已经重建好，我们只需要考虑将root节点按上
4.所以递归：首先利用先序遍历的首节点也就是根节点创建一个树对象，然后递归左子树和右子树，递归的出口是只有一个节点的时候，返回当前节点,没有节点时返回None
5.注意：没有节点时的判断应该是len（pre）

3.实现

    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre)==0:
            return None
        elif len(pre)==1:
            return TreeNode(pre[0])
        else:
            newTree=TreeNode(pre[0])
            index=tin.index(pre[0])
            #left中需要加一 是因为list的切片是左闭右开的
            newTree.left=self.reConstructBinaryTree(pre[1:index+1],tin[:index])
            newTree.right=self.reConstructBinaryTree(pre[index+1:],tin[index+1:])
            return newTree

4.相关知识点

1.先、中、后序遍历的三种方式
2.如何构建一个二叉树：我，竟然没有写树与树的算法

3.list的切片时要注意：左闭右开