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

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

---

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)