原创
请记住当时浮躁的自己
今天女朋友特别漂亮，我和她一起特别高兴，然后回来年轻气盛的浑身燥热睡不着觉，就半夜来更一发
int sumhappy=0;//初始happy为0；
int state=0;//初始状态为0
if（见女朋友）state=1；//激发状态
while（state）
{
sumhappy++；//故意死循环
}
看题！
树的同构
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
图1
image
图2
image
现给定两棵树，请你判断它们是否是同构的。
输入格式:
输入给出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
为何你当时如此浮躁，think for yourself！
其实仔细分析一下这个题也不难，刚才跑去舍友郑板桥（化名）那里热心为他讲解这个题，结果强行装逼，“热于助人”成了车祸现场。
只能自己理解不算真正理解，饺子熟悉透就能从茶壶里倒出来（这句话有点牵强到不能再牵强）
强者自渡，圣者渡人。
蒟蒻不敢以圣者自诩，就当serve people heart and soul啦。
分析该题，首先任何一个数据结构题，不管是线性结构，树，图，都得用相应的存储结构，这个题明显是个树，思考一下该题用什么存比较好呢
第二，你会发现输入并不是按照从父节点到孩子节点顺序来的，那你把树的各个节点存起来，如何记录节点之间的逻辑关系？并且如何表示这个树？不然你只是把树存储起来，而将无法对树进行任何操作。
第三，树的同构的条件？
一个特别有用的哲学策略叫“先解决首要矛盾，再解决次要矛盾”。首先第一第二问
题可以归结为解决存储数据问题，建立一个能反映逻辑结构的二叉树存放数据。
建立二叉树需要struct结构体，其中必包含数据域（字母）指针域（两个指针分别
指向左右孩子）这里可以用结构数组存。仔细读题你会发现，输入的形式特别像图
中的邻接表，唯一的区别就是图表头后边接的是所有邻接点，而该处树只接左右孩
子两个。借鉴图邻接表的思想我们可以用结构数组存（题目给了咱们使用结构数组
的充分条件，每个节点都有且仅有三个信息）。
第二个问题，核心，同构树的判断，哦，插菊花，呀呸！输入法有毛病！插句话，
解决问题要形成自己的习惯，这样你解决问题的经验就能时时帮助你了。稍微复杂
的问题可以考虑，递归，贪心，动态规划。这三思想掌握熟练就好像有三驾马车带
你到处碾压大学课上编程题了。继续该题，同构的树相同的节点集合有相同的父节
点，也可以说两颗树相同父节点下面要么左孩子是相等的且与孩子是相等的，要么
左孩子与右孩子相等且右孩子与左孩子相等，嗷嗷嗷，对，判断条件明朗起来，而
且明显这个判断条件对树的任意节点都适用。主体判断条件弄完了，边角的特殊情
况也要考虑，即孩子节点是否为空？把空的情况考虑进去，而且明显这些判断条件
对树的任意节点都适用，只需要把树节点遍历一遍就OK了，用递归遍历树，对，
这是常识。
到这儿，就相当于成功了一半，剩下的一半就是把刚才的分析翻译成代码，写代码可以适当加快速度。
上代码！
#include<stdio.h>
#define MAX 11
#define Null -1
//因为结构数组是通过下标索引，不是通过指针索引，注意要区分开NULL，故此处使用Null定义值为-1。
struct Treenode{
char val;
int left;
int right;
}tree1[MAX],tree2[MAX];//相当于声明变量tree1，tree2了。
//int ismark[MAX]={0};注*
int buildtree(struct Treenode T[])//这里注意一下树的建立函数形参形式。
{
int ismark[MAX]={0};//标记是否有前驱，没有前驱就是root根节点了。
int n,i;
scanf("%d",&n);
getchar();
if(n<=0)return Null;
else
{
for(i=0;i<n;i++)
{
char le,ri;
scanf("%c %c %c",&T[i].val,&le,&ri);
getchar();
//吃掉回车
if(le!='-')
{
T[i].left=le-'0';
ismark[T[i].left]=1;
}
else
T[i].left=Null;
if(ri!='-')
{
T[i].right=ri-'0';
ismark[T[i].right]=1;
}
else
T[i].right=Null;
}
for(i=0;i<n;i++)
{
if(!ismark[i])return i;
}
}
}
int compare_tree(int tree1root,int tree2root)
{
if(tree1root==Null&&tree2root==Null)
return 1;
//第一次测试正确
if((tree1root==Null&&tree2root!=Null)||(tree2root==Null&&tree1root!=Null))
return 0;
//第一次测试正确
if(tree1[tree1root].val!=tree2[tree2root].val)
return 0;
//第一次测试正确
if(tree1[tree1root].left==Null&&tree2[tree2root].left==Null)
return compare_tree(tree1[tree1root].right,tree2[tree2root].right);
//第一次测试正确
if(tree1[tree1root].left!=Null&&tree2[tree2root].left!=Null)
{
if(tree1[tree1[tree1root].left].val==tree2[tree2[tree2root].left].val)
return compare_tree(tree1[tree1root].left,tree2[tree2root].left)&&compare_tree(tree1[tree1root].right,tree2[tree2root].right);
//第一次测试正确
else
return compare_tree(tree1[tree1root].left,tree2[tree2root].right)&&compare_tree(tree1[tree1root].right,tree2[tree2root].left);
//第一次测试正确
}
}
//比较函数内无bug
int main()
{
int root1,root2;
root1=buildtree(tree1);
root2=buildtree(tree2);
//printf("%d\n%d",root1,root2);
//第二次测试找到bug
if(compare_tree(root1,root2))
printf("Yes\n");
else
printf("No\n");
}
//主函数较简单应该不会出bug。
注*地方出现bug。
不行，从前天凌晨0：30开始写这篇，写好代码之后运行程序结果不对，有bug，然后直到到刚刚才找出来，找bug用了3~4个小时，文章也耽误了30多小时。都怨自己作，明知道数组会记录值还我放在全局变量的位置，因为当时想着这个题就只有一次输入一个输出，就放外面吧，这样计算机轻松点，，其实这个题结构数组输入两次，分别是tree1，tree2。ismark[]数组必须重新开始。没啥算法，就是逻辑清晰了就好。
有时候不沉下心来以为自己会了懂了，其实并不会并不懂，等完全独立解决问题时就能出考验人的真本事。
网友评论