判断t1树是否包含t2树全部的拓扑结构

[编程题]判断t1树是否包含t2树全部的拓扑结构

热度指数：1115 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定彼此独立的两棵二叉树，判断 t1 树是否包含 t2 树全部的拓扑结构。

设 t1 树的边集为 E1，t2 树的边集为 E2，若 E2 是 E1 的子集，则表示 t1 树包含 t2 树全部的拓扑结构。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树 t1 的总节点个数，root 表示二叉树 t1 的根节点。

以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

第 n+2 行输入两个整数 m 和 root，n 表示二叉树 t2 的总节点个数，root 表示二叉树 t2 的根节点。

以下 m 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:

如果 t1 树包含 t2 树全部的拓扑结构，则输出 "true"，否则输出 "false"。

示例1

输入

输出

true

备注:

算法知识视频讲解

Python

毓毓子最可爱

#数据的输入处理
#树1
n, r1 = list(map(int, input().split()))
#将树定义为字典
tree1 = {}
for _ in range(n):
    x, left, right = list(map(int, input().split()))
    #以元祖的形式定义子树
    tree1[x] = (left, right)
#树2
m, r2 = list(map(int, input().split()))
tree2 = {}
for _ in range(m):
    x, left, right = list(map(int, input().split()))
    tree2[x] = (left, right)
    
# ==============================
#检查x,以及它作为根时的子树是否在tree 1里面
def checkNode(x) -> bool: 
    if not x in tree1:
        return False
    #取出子树
    l2, r2 = tree2[x]
    #如果子树非空，但是不在树1中
    if l2 and l2 not in tree1[x]:
        return False
    if r2 and r2 not in tree1[x]:
        return False
    return True
# 遍历tree 2， 查每个节点和它左右的链接
def bfs(tree, root): 
    queue = [root]
    #层次遍历
    while queue:
        x = queue.pop()
        if not checkNode(x):
            return False
 
        if tree[x][0]: # left
            queue.append(tree[x][0])
        if tree[x][1]: # right
            queue.append(tree[x][1])
    
    return True

if bfs(tree2, r2):
    print('true')
else:
    print('false')

发表于 2021-06-14 19:13:11 回复(0)