剑指Offer - 九度1520 - 树的子结构
2013-11-30 22:17
- 题目描述：
输入两颗二叉树A，B，判断B是不是A的子结构。
- 输入：
输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行一个整数n,m(1<=n<=1000,1<=m<=1000)：n代表将要输入的二叉树A的节点个数（节点从1开始计数），m代表将要输入的二叉树B的节点个数（节点从1开始计数）。接下来一行有n个数，每个数代表A树中第i个元素的数值，接下来有n行，第一个数Ki代表第i个节点的子孩子个数，接下来有Ki个树，代表节点i子孩子节点标号。接下来m+1行，与树A描述相同。
- 输出：
对应每个测试案例，
若B是A的子树输出”YES”(不包含引号)。否则，输出“NO”（不包含引号）。
- 样例输入：
7 3
8 8 7 9 2 4 7
2 2 3
2 4 5
0
0
2 6 7
0
0
8 9 2
2 2 3
0
0 1 1
2
0
3
0
- 样例输出：
YES
NO
- 提示：
B为空树时不是任何树的子树。
题意分析：
给定两棵二叉树，判断树B是否为树A的子结构。题目中的输入输出方式有点问题，不过无伤大雅。对于“子结构”的话，可以参考下面的例子：
只要能把B树和A树中的一部分重合起来，就定义B树是A树的子结构。递归求解即可，细节应该不需要赘述了。如果A树、B树的节点数分别为m、n，则时间复杂度O(m * n)，因为递归过程中对于每个A中的节点，都需要将B树的结构验证一遍，验证失败时可以提前结束递归，但平均复杂度仍是O(n)，所以综合起来是O(m * n)。下面是ac代码。
// 652327 zhuli19901106 1520 Accepted 点击此处查看所有case的执行结果 1048KB 2486B 10MS
//
#include <cstdio>
using namespace std; const int MAXN = ;
int a[MAXN][];
int b[MAXN][];
int c[MAXN];
int na, nb;
int ra, rb; bool is_subtree(const int a[][], const int b[][], int ia, int ib)
{
if(a == NULL || b == NULL){
return false;
}
if(ia < || ia > na - ){
return false;
}
if(ib < || ib > nb - ){
return false;
} if(a[ia][] == b[ib][]){
bool ret1, ret2; if(b[ib][] != -){
ret1 = is_subtree(a, b, a[ia][], b[ib][]);
}else{
ret1 = true;
} if(b[ib][] != -){
ret2 = is_subtree(a, b, a[ia][], b[ib][]);
}else{
ret2 = true;
} return (ret1 && ret2);
}else{
return false;
}
} int main()
{
int i, j;
int x, y; while(scanf("%d%d", &na, &nb) == ){
for(i = ; i < na; ++i){
for(j = ; j < ; ++j){
a[i][j] = -;
}
}
for(i = ; i < nb; ++i){
for(j = ; j < ; ++j){
b[i][j] = -;
}
} for(i = ; i < na; ++i){
scanf("%d", &x);
a[i][] = x;
c[i] = ;
}
for(i = ; i < na; ++i){
scanf("%d", &j);
if(j == ){
scanf("%d", &x);
a[i][] = x - ;
++c[x - ];
}else if(j == ){
scanf("%d%d", &x, &y);
a[i][] = x - ;
a[i][] = y - ;
++c[x - ];
++c[y - ];
}
}
ra = -;
for(i = ; i < na; ++i){
if(c[i] == ){
ra = i;
}
} for(i = ; i < nb; ++i){
scanf("%d", &x);
b[i][] = x;
c[i] = ;
}
for(i = ; i < nb; ++i){
scanf("%d", &j);
if(j == ){
scanf("%d", &x);
b[i][] = x - ;
++c[x - ];
}else if(j == ){
scanf("%d%d", &x, &y);
b[i][] = x - ;
b[i][] = y - ;
++c[x - ];
++c[y - ];
}
}
rb = -;
for(i = ; i < nb; ++i){
if(c[i] == ){
rb = i;
}
} // you can't put this if() up front, if na > 0 && nb == 0, then the input data for a is ignored
if(na <= || nb <= ){
printf("NO\n");
continue;
} if(ra == - || rb == -){
// there is at least one invalid tree
printf("NO\n");
continue;
} for(i = ; i < na; ++i){
if(is_subtree(a, b, i, rb)){
break;
}
}
if(i < na){
printf("YES\n");
}else{
printf("NO\n");
}
} return ;
}