【python】1本の木が別の木のサブツリーかどうかを判断する

タイトル:
互いに独立した2本のツリーAとBについて、効率的なアルゴリズムを作成し、Aに1本のツリーがBツリーのトポロジー構造と完全に同じであるかどうかを確認します.
2本の二叉木のヘッドノードAとBを指定し、AにBと同じサブツリーが存在するかどうかを表すbool値を返します.
2つの方法:
1.2つのサブツリーA,Bを、同じ遍歴方式(前、後、中)で文字列strA,strBにシーケンス化する.strBがstrAに含まれているかどうかを判断します.
2.反復.
メソッド1コード:

# -*- coding:utf-8 -*-

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class IdenticalTree:
    def chkIdentical(self, A, B):
        # write code here
        if A==None or B==None:
            return False
        strA=self.pre(A)
        strB=self.pre(B)
        if strB in strA:
            return True
        else:
            return False
    def pre(self,root):
        res=''
        if root==None:
            return '#!'
        
        res+=str(root.val)+'!'
        res+=self.pre(root.left)
        res+=self.pre(root.right)
        return res

メソッド2コード:#リファレンスリンクhttp://blog.csdn.net/u012560212/article/details/72731313

# Definition for a binary tree node.  
# class TreeNode(object):  
#     def __init__(self, x):  
#         self.val = x  
#         self.left = None  
#         self.right = None  
  
class Solution(object):  
    def isSubtree(self, A, B):  #        ，     A      ，          ，  B      
        """ 
        :type s: TreeNode 
        :type t: TreeNode 
        :rtype: bool 
        """  
        if not A:  
            return False  
              
        return self.isEqual(A,B) or self.isSubtree(A.left,B) or self.isSubtree(A.right,B)  
        #  or  ，        s    t  ，   True  
          
          
    def isEqual(self,S,T):  # S    ，  S T      
        if not S and not T:  
            return True  
        if S and T:  
            if S.val!=T.val:  
                return False  
            return self.isEqual(S.left,T.left) and self.isEqual(S.right,T.right)  
        else:  
            return False