子樹
有兩個不同大小的二叉樹: T1 有上百萬的節(jié)點; T2 有好幾百的節(jié)點。請設(shè)計一種算法,判定 T2 是否為 T1的子樹。
子樹
def isEqual(self,T1, T2):
if T1 == None or T2 == None:
return T1 == T2;
if T1.val != T2.val:
return False
return self.isEqual(T1.right, T2.right) and self.isEqual(T1.left, T2.left)
def isSubtree(self, T1, T2):
# write your code here
if T2 == None:
return True
if T1 == None:
return False
if self.isEqual(T1, T2):
return True
if self.isSubtree(T1.right, T2) or self.isSubtree(T1.left, T2):
return True
return False