7-3 树的同构

题目描述

判断给出的两棵树是否是同构的(同构-即左右子树可以相互交换位置)

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

思路

刚开始听了MOOC上说用静态链表(简单来说就是数组,只不过每个元素带有指针效果的元素)后这么想的:读入需要两个inArray,再根据这两个Array构造两个满二叉树的char型数组,然后用递归写一个cmp在满二叉树的char型数组上比较。实在太麻烦了。

然后就用了MOOC上的方法。搞了全局变量,简直不要太舒服。

最后一个边界条件(n=0)引起的段错误调的我ooxx

难点

怎么组织你的数据,就像老师讲的:

  • 你打算怎么储存两棵树
  • 怎么找到根节点(这个简单)
  • 怎么比较同构
    1和3我现在都还是无法驾驭。1是熟练掌握数据结构的应用,3是写递归程序。

体会与感想

深深地体会到了大神的代码和我自己的代码之间的区别(100+行都写不完和60行AC的差距)orz

当你函数的参数≥四个并且还是在反复传同一个参数的时候,你就该想想你的思路是不是不太对了。

有时候全局变量该用就得用,否则到时候难受的是你自己。

main函数里东西越少越好,代码质量越高,可读性越好。

递归函数感觉还是比较虚,边界条件有时理不清。

尽可能地检查边界条件(极小与极大)。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#define max 10
#define null -1
using namespace std;

struct node {
char element;
int left;
int right;
}tree1[max], tree2[max];

int build(node * tree);
bool isomorphic(int r1, int r2);

int main(int argc, char const *argv[]) {
freopen("D:\\SJTU\\Freshman Summer\\DS\\test.txt", "r", stdin);
int r1 = 0, r2 = 0;
r1 = build(tree1);
r2 = build(tree2);
if (r1!=-1 && r2!=-1) {
if (isomorphic(r1,r2)) cout << "Yes";
else cout << "No";
}else if (r1==-1 && r2==-1) {
cout << "Yes";
}else cout << "No";
return 0;
}

bool isomorphic(int r1, int r2)
{
if (r1==null && r2==null) return true;
if (r1==null || r2==null) return false;
int n1 = 0, n2 = 0;
if (tree1[r1].left==null) n1++;
if (tree1[r1].right==null) n1++;
if (tree2[r2].left==null) n2++;
if (tree2[r2].right==null) n2++;
if (n1!=n2) return false;
if (tree1[r1].element!=tree2[r2].element) return false;
if (n1==2) return true;
else if (n1==1) {
if (tree1[r1].left==null&&tree2[r2].left==null) {
return isomorphic(tree1[r1].right,tree2[r2].right);
}
else if (tree1[r1].left==null&&tree2[r2].right==null) {
return isomorphic(tree1[r1].right,tree2[r2].left);
}
else if (tree1[r1].right==null&&tree2[r2].left==null) {
return isomorphic(tree1[r1].left,tree2[r2].right);
}
else if (tree1[r1].right==null&&tree2[r2].right==null) {
return isomorphic(tree1[r1].left,tree2[r2].left);
}
}
else if (n1==0) {
if (tree1[tree1[r1].left].element==tree2[tree2[r2].left].element) {
return isomorphic(tree1[r1].left,tree2[r2].left) && isomorphic(tree1[r1].right,tree2[r2].right);
}else{
return isomorphic(tree1[r1].left,tree2[r2].right) && isomorphic(tree1[r1].right,tree2[r2].left);
}
}
return true;
}

int build(node * tree)
{
int n;cin >> n;
if (n==0) return -1;
int * select = new int [n];
char le, ri;
for (int i = 0; i < n; i++) select[i] = 0;
for (int i = 0; i < n; i++) {
cin >> tree[i].element >> le >> ri;
if (le!='-') {
tree[i].left = le - '0';
select[tree[i].left] = 1;
}else tree[i].left = null;
if (ri!='-') {
tree[i].right = ri - '0';
select[tree[i].right] = 1;
}else tree[i].right = null;
}
int ret = 0;
for (int i = 0; i < n; i++) {
if (select[i]==0) {
ret = i;
break;
}
}
delete [] select;
return ret;
}