每天一道编程题——判断t1树是否包含t2树的全部拓扑结构

原理:
遍历t1树,然后将其每个子树与t2作比较。最后把所有结果进行或运算即可。
复杂度:
O(N*M) t1节点数N;t2节点数M


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Node:
def __init__(self, value, left=None, right=None):
self.left = left
self.right = right
self.value = value
def check(h, t2):
# t2为None,说明t2已经遍历完了
if t2 == None: return True
if h == None or h.value != t2.value: return False
# 只有t2左右两边都能完整地遍历,才能说明t1子树h包含t2树的全部拓扑结构
return check(h.left, t2.left) and check(h.right, t2.right)
def contains(t1, t2):
# 若t1为叶子结点
if t1.left is None or t1.right is None:
return check(t1, t2)
else:
# 前序遍历t2,将他们的返回值进行或运算
return check(t1, t2) or contains(t1.left, t2) or contains(t1.right, t2)
t1 = Node(1, Node(2, Node(4, Node(8), Node(9)), Node(5, Node(10))), Node(3, Node(6), Node(7)))
t2 = Node(2, Node(4, Node(8)), Node(5))
# t2=Node(9)
print contains(t1, t2)
文章目录
|