Skip to content

11213: 【原1213】same

题目

题目描述

author: DS TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1213 

Description

给出两棵二叉树的结构以及各个结点的权值,判断这两棵二叉树是否相同。所谓两棵树相同指的是树的形状及对应结点的值相同。必须使用二叉树类来实现,不要求重载操作符。

Input Format

输入文件一共包含N+M+2行。

第一行含有一个正整数N,代表第一棵树中的结点总数。

接下来的N行,给出的是第一棵树的信息,每行包含三个整数。其中第i行的三个整数Pi,Qi,Vi,代表结点i的左孩子为Pi,右孩子为Qi,结点i自身的权值为Vi。若Pi=0,则表明结点i没有左孩子。同样的,若Qi=0,则表明结点i没有右孩子。(第i行指的是这N行中的第i行)

接下来一行,含有一个正整数M,代表第二棵树中的结点总数。

再接下来的M行,给出的是第二棵树的信息,每行包含三个整数。其中第j行的三个整数Pj,Qj,Vj,代表结点j的左孩子为Pj,有孩子为Qj,结点j自身的权值为Vj。若Pj=0,则表明结点j没有左孩子。同样的,若Qj=0,则表明结点j没有有孩子。(第j行指的是这M行中的第j行)

Output Format

若两棵树相同,则输出'Y',否则输出'N'。(均不包含引号)

Sample Input1

4
0 0 1
3 1 2
0 0 3
0 2 4
4
0 4 4
0 0 3
0 0 1
2 3 2

Sample Output1

Y

Sample Input2

4
0 0 1
3 1 2
0 0 3
0 2 4
4
0 4 3
0 0 3
0 0 1
2 3 2

Sample Output2

N

Limit

对于所有的数据,均满足1<=N,M<=100000

对于所有的数据,均满足0<=Pi,Qi,Pj,Qj<=N

对于所有的数据,均满足-2147483648<=Vi,Vj<=2147483647

对于所有的数据,均保证给出的前N+1行是一棵二叉树,后M+1行是一棵二叉树

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!