练习内容：

判断一个二叉树T1是否是另一颗二叉树T2的子树。(T2>T1)

要求：时间复杂度O(N)，空间复杂度O(1)

正文内容提要：

1.morris遍历实现T1，T2的先序序列化。

2.kmp算法判断T1与T2的序列化结果(T2>T1)

　　（1）如果seralize(T1)是seralize(T2)的子串，则T1是T2的子树

　　（2）否则，T1不是T2的子树

1.创建类描述树结构

1 class MyProperty: 2     def __init__(self, get_attrib_func): 3         self.get_attrib_func = get_attrib_func 4         self.set_attrib_func = None 5  6     def __set__(self, instance, value): 7         if not self.set_attrib_func: 8             raise AttributeError("can't set attribute") 9         self.set_attrib_func(instance, value)10 11     def __get__(self, instance, owner):12         return self.get_attrib_func(instance)13 14     def setter(self, set_attrib_func):15         self.set_attrib_func = set_attrib_func16         return self17 18 19 class Node:20     def __init__(self, value):21         self.value = value22         self.__left = None23         self.__right = None24 25     @MyProperty26     def left(self):27         return self.__left28 29     @left.setter30     def left(self, node):31         self.__left = node32 33     @MyProperty34     def right(self):35         return self.__right36 37     @right.setter38     def right(self, node):39         self.__right = node

2.使用morris遍历，实现二叉树的先序序列化

1 def morris_pre_serialize(head): 2     if not head: 3         return 4     string = [] 5     cur = head 6     most_right = None 7     while cur != None: 8         most_right = cur.left 9         if most_right != None:10             while most_right.right != None and most_right.right != cur:11                 most_right = most_right.right12 13             if most_right.right == None:  # 第一次到达cur节点14                 string.append("{}{}".format(cur.value, "_"))15                 most_right.right = cur16                 cur = cur.left17                 continue18             else:19                 most_right.right = None  # 第二次到达cur节点20                 string.append("#_")21 22         else:23             string.append(str(cur.value) + "_")24             string.append("#_")25         cur = cur.right26     else:27         string.append("#_")28 29     return "".join(string)

3.实现kmp算法

1 def kmp(str_x, str_y): 2  3     def __get_nexts(str_x): 4         if str_x is None: 5             return None 6  7         length = len(str_x) 8         if length == 1: 9             return [-1]10 11         nexts = [0] * length12         nexts[0] = -113         nexts[1] = 014         i1, i2 = 2, 115         while i1 < length:16             if str_x[i1 - 1] == str_x[nexts[i2]]:17                 nexts[i1] = nexts[i2] + 118                 i2, i1 = i1, i1 + 119             elif nexts[i2] != -1:20                 i2 = nexts[i2]21             else:22                 nexts[i1] = 023                 i2, i1 = i1, i1 + 124         return nexts25 26 27     if str_x is None or str_y is None or len(str_y) < 1 or len(str_x) < len(str_y):28         return -129 30     len_str_x, len_str_y = len(str_x), len(str_y)31 32     i1, i2 = 0, 033 34     nexts = __get_nexts(str_y)35 36     while i1 < len_str_x and i2 < len_str_y:37         if str_x[i1] == str_y[i2]:38             i1, i2 = i1 + 1, i2 + 139         elif nexts[i2] != -1:40             i2 = nexts[i2]41         else:42             i1 += 143     return i1 - i2 if i2 == len_str_y else -1

4.结合morris遍历，kmp子串判断，实现子树的判断。时间复杂O(N), 空间复杂度O(1)

1 def is_sub_tree(head1, head2): 2     if head1 is None or head2 is None: 3         return False 4  5     str1 = morris_pre_serialize(head1) 6     str2 = morris_pre_serialize(head2) 7  8     str1, str2 = (str2, str1) if len(str1) < len(str2) else (str1, str2) 9 10     ret = kmp(str1, str2)11 12     return True if ret != -1 else False

 5.简单测试代码

1 if __name__ == "__main__": 2     tree_1 = Node(1) 3     tree_1.left = Node(2) 4     tree_1.right = Node(3) 5     tree_1.left.left = Node(4) 6     tree_1.left.right = Node(5) 7     tree_1.right.left = Node(6) 8     tree_1.right.right = Node(7) 9 10     tree_2 = Node(3)11     tree_2.left = Node(6)12     tree_2.right = Node(7)13     tree_2.left.right = Node(8)14     # tree_2 is not tree_1's sub tree15     print(is_sub_tree(tree_2, tree_1))  # False16     print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")17     tree_3 = Node(3)18     tree_3.left = Node(6)19     tree_3.right = Node(7)20     # tree_3 is tree_1's sub tree21     print(is_sub_tree(tree_1, tree_3))  # True