04_ツリーの再構築【python】

1.問題の説明
ツリーの前順および中順の結果を入力し、ツリーを再構築します.入力された前シーケンスおよび中シーケンスの結果に重複する数値が含まれていないと仮定します.例えば、前シーケンス遍歴シーケンス{1,2,4,7,3,5,6,8}と中シーケンス遍歴シーケンス{4,7,2,1,5,3,8,6}を入力すると、ツリーが再構築され、戻ります.
2.考え方
まず、二叉木の条件反射といえば再帰1であるべきである.先に巡回する最初のノードはルートノードであるに違いない.中序遍歴、ルートノードの前は左サブツリー、後ろは右サブツリー3.数学的帰納法の考え方を用いて,現在が最後のステップであると仮定すると,左サブツリーと右サブツリーが再構築され,rootノードを上4に押すことを考慮する必要がある.したがって再帰:まず、最初のノードであるルートノードを用いてツリーオブジェクトを作成し、左サブツリーと右サブツリーを再帰する.再帰の出口が1つのノードしかない場合、現在のノードに戻り、ノードがない場合は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.先、中、後の順に巡る3つの方式2.どのように1つの二叉木を構築します:私、意外にも木と木のアルゴリズムを書いていません
3.listのスライス時注意:左閉じ右開き