C1092 - 相似的二叉树
题目描述
二叉树的相似判断是指检查两个二叉树在结构上是否相同，而不一定考虑节点的具体值。具体来说，如果两个二叉树在结构上对应的节点都具有相同的孩子结构（即每个节点都有相同数目的孩子，左孩子和右孩子的存在与否相同），则认为这两棵树是相似的。
比如下面的两个二叉树就是相似的：
上面这个两个二叉树与下面的二叉树就不是相似的：
现在给出两个二叉树的节点信息，请你编写个程序来判断它们是否是相似的
输入格式
2棵二叉树的信息：
第1行，一个正整数n，代表第1个二叉树的n个节点数
接下来n行，每行一个三元组（id, left, right)，用于描述二叉树的一个节点信息
接下来1行，一个正整数m，代表第2个二叉树的m个节点信息
接下来m行，每行一个三元组（id, left, right)，用于描述二叉树的一个节点信息
设给定的二叉树拥有n个节点，每个节点中是一个0 - (n - 1)的编号数据，不会出现重复的编号数据
三元组（id, left, right)的含义是：
- id：代表当前节点的编号
- left: 当前节点的左子节点的编号
- right: 当前节点的右子节点的编号
不存在左子节点或右子节点时，left/right为-1
具体可以参考输入输出样例说明
输出格式
第1行，相似判定结果，代表两个二叉树是否是相似的，相似则输出Y，否则输出N
第2行，第1棵二叉树的高度
第3行，第2棵二叉树后序遍历结果，每个节点数据使用一个空格分隔
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 5 0 1 3 1 2 -1 3 4 -1 2 -1 -1 4 -1 -1 5 1 -1 -1 3 -1 -1 2 3 -1 4 0 2 0 1 -1 |
Y 3 1 0 3 2 4 |
| 5 0 1 3 1 2 -1 3 4 -1 2 -1 -1 4 -1 -1 5 4 0 2 0 1 -1 2 -1 3 1 -1 -1 3 -1 -1 |
N 3 1 0 3 2 4 |
输入输出样例说明
第1组输入输出样例对应的两个二叉树是：
它们是相似的，第1棵二叉树的高度是3，第2棵二叉树的后序遍历结果为：1 0 3 2 4
第2组输入输出样例对应的两个二叉树是：
它们是不相似的，第1棵二叉树的高度是3，第2棵二叉树的后序遍历结果为：1 0 3 2 4
数据范围与提示
对于100%的数据满足：$1 \le n, m \le 10$
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式