PTA 树的同构(25 分)

7-1 树的同构(25 分)

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。

图1

图2

现给定两棵树,请你判断它们是否是同构的。

输入格式:

输入给出2棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数N (≤10),即该树的结点数(此时假设结点从0到N−1编号);随后N行,第i行对应编号第i个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。

输出格式:

如果两棵树是同构的,输出“Yes”,否则输出“No”。

输入样例1(对应图1):

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

输出样例1:

Yes

输入样例2(对应图2):

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

输出样例2:

Noemmmmmm   声明,下面的骚操作适合节点和边都比较少的,别怪我没提醒,多了就不对了,但是骚一字就够了
#include <bits/stdc++.h>// 根据度数判断
using namespace std;
const int maxn = 11;
int countsa[maxn];
int countsb[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    char a,b,c;

    for(int i=0;i<n;i++)
    {
        int add = 2;
        cin>>a>>b>>c;
        if(b=='-') add--;
        if(c=='-') add--;
        countsa[a-'A'] +=add;
    }
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int add = 2;
        cin>>a>>b>>c;
        if(b=='-') add--;
        if(c=='-') add--;
        countsb[a-'A']+=add;
    }
    if(n==1) {cout<<"No"<<endl;
    return 0;}
    int i;
    for(i=0;i<n;i++)
    {
        if(countsa[i]!=countsb[i])
        {
            cout<<"No"<<endl;
            break;
        }
    }
    if(i==n)
        cout<<"Yes"<<endl;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏葡萄城控件技术团队

深入CSS,让网页开发少点“坑”

 通常我们在学习CSS的时候,感觉语法很容易掌握,实际应用中却碰到各式各样难以填补的“坑”,为避免大家受到同样的困惑与不解,本文详细讲解了CSS中优先级和Sta...

1749
来自专栏小樱的经验随笔

线段树入门总结

线段树的入门级 总结       线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。       对于...

3536
来自专栏PPV课数据科学社区

【学习】K近邻算法基础:KD树的操作

Kd-树概念 Kd-树其实是K-dimension tree的缩写,是对数据点在k维空间中划分的一种数据结构。其实,Kd-树是一种平衡二叉树。 举一示例: 假设...

2865
来自专栏编程

新知识 用Python从零开始构造决策树

起步 本章介绍如何不利用第三方库,仅用python自带的标准库来构造一个决策树。 熵的计算公式: ? 对应的python代码: ? 条件熵的计算 根据计算方法:...

3248
来自专栏Java Edge

二分查找复杂度分析实战演练

3328
来自专栏木子昭的博客

递归并非万能

递归的确简洁, 但性能很差, 因为它进行了大量重复的计算, 如果用递归运算做乘法, 5!*4! = 5*4*3*2*1 * 4*3*2*1显然4!完全可以算...

2555
来自专栏程序员叨叨叨

8.4 CG 标准函数库

和 C 的标准函数库类似,Cg 提供了一系列内建的标准函数。这些函数用于执行数学上的通用计算或通用算法(纹理映射等),例如,需要求取入射光线的反射光线方向向量可...

935
来自专栏玄魂工作室

Python数据结构与算法-在M个数中找K个最小的数

比如输入10,-9,0,100,90,1,4,-9;找到最小的3个数为:-9,-9,0

861
来自专栏mathor

matlab—进阶绘图

这里我们要讲的是画一些与对数(log)有关的图像,这里的log,既可以是图像是log,又可以是坐标轴是log,我们接下来用一个例子来说明

923
来自专栏技术博文

PHP实现经典算法

前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序。 $arr = array(1,43,54,62,21,6...

2604

扫码关注云+社区