剣指OFFERの木のサブ構造(九度OJ 1520)
15998 ワード
タイトルの説明:
2本のツリーA,Bを入力し,BがAのサブ構造であるか否かを判断する.
入力:
入力には複数のテストサンプルが含まれ、入力はEOFで終了します.各テストケースについて、入力する1行目の整数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 。問題解決の考え方：
この問題には穴があり,まず問題はnとmの範囲が0ではないことを要求するが,試験例では3番目と4番目がそれぞれ1番目の木空と2番目の数空の特殊な場合である可能性がある.したがって、ここでは、scanf("%d%d",&n,&m)のときにmnに制限された範囲に注意する.
また、使用例では、単一の葉が与えられていない場合、1と入力すると、1つのノードしかなく、左サブツリーノードであることに注意してください.
例えば子供が1人しかいない場合に入力したのは
また、このテーマの主な考えです.まず私たちが採用したのは依然として前回のテーマで使用した構造の木で、主な思想は左のこの木の要素がなくて、右の木と比較することです.違う場合は、左の子供ノードを比較します.すべての木を巡るまで.
比較を行う場合,右側の木が空であるか,左の判断頂点が空であるかを判断し,比較の要素が異なることが発見されると,比較に失敗したことを証明する.
主なコードは、本のコードを真似て行い、自分で書いた総出BUG、あれ.
int testForCompare(TreeArr *t1,int t1i,TreeArr *t2){
int result = 0;
if(t1i != 0 && t2->arr[0].num != 0){
if(t1->arr[t1i].num == t2->arr[1].num)
result = compare(t1,t1i,t2,1);
if(!result)
result = testForCompare(t1,t1->arr[t1i].lchild,t2);
if(!result)
result = testForCompare(t1,t1->arr[t1i].rchild,t2);
}
return result;
};
int compare(TreeArr *t1,int t1i,TreeArr *t2,int t2i){
if(t2i == 0)
return 1;
if(t1i == 0)
return 0;
if(t1->arr[t1i].num != t2->arr[t2i].num)
return 0;
return compare(t1,t1->arr[t1i].lchild,t2,t2->arr[t2i].lchild)&&compare(t1,t1->arr[t1i].rchild,t2,t2->arr[t2i].rchild);
}すべてのコード:
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1005
typedef struct treeelement{
int num;
int lchild;
int rchild;
}TreeElement;
typedef struct treearr{
TreeElement arr[MAXSIZE];
}TreeArr;
int testForCompare(TreeArr *t1,int t1i,TreeArr *t2);
int compare(TreeArr *t1,int t1i,TreeArr *t2,int t2i);
int main(void){
int n,m,i,nchild,n1,n2;
TreeArr *t1 = (TreeArr *)malloc(sizeof(TreeArr));
TreeArr *t2 = (TreeArr *)malloc(sizeof(TreeArr));
while(scanf("%d %d",&n,&m) != EOF){
//....initialize the tree
for(i=0;i<1000;i++){
t1->arr[i].num = 0;
t1->arr[i].lchild = 0;
t1->arr[i].rchild = 0;
t2->arr[i].num = 0;
t2->arr[i].lchild = 0;
t2->arr[i].rchild = 0;
}
t1->arr[0].num = n;
t2->arr[0].num = m;
//.....input the first tree
for(i=1;i<=n;i++){
scanf("%d",&t1->arr[i].num);
}
for(i=1;i<=n;i++){
scanf("%d",&nchild);
if(nchild == 2){
scanf("%d %d",&n1,&n2);
t1->arr[i].lchild = n1;
t1->arr[i].rchild = n2;
}else if(nchild == 1){// ？
scanf("%d",&n1);
t1->arr[i].lchild = n1;
}else if(nchild == 0){
}
}
//........input the second tree
for(i=1;i<=m;i++){
scanf("%d",&t2->arr[i].num);
}
for(i=1;i<=m;i++){
scanf("%d",&nchild);
if(nchild == 2){
scanf("%d %d",&n1,&n2);
t2->arr[i].lchild = n1;
t2->arr[i].rchild = n2;
}else if(nchild == 1){// ？
scanf("%d",&n1);
t2->arr[i].lchild = n1;
}else if(nchild == 0){
}
}
//testing for compare
if(testForCompare(t1,1,t2))
printf("YES
");
else
printf("NO
");
}
return 0;
};
int testForCompare(TreeArr *t1,int t1i,TreeArr *t2){
int result = 0;
if(t1i != 0 && t2->arr[0].num != 0){
if(t1->arr[t1i].num == t2->arr[1].num)
result = compare(t1,t1i,t2,1);
if(!result)
result = testForCompare(t1,t1->arr[t1i].lchild,t2);
if(!result)
result = testForCompare(t1,t1->arr[t1i].rchild,t2);
}
return result;
};
int compare(TreeArr *t1,int t1i,TreeArr *t2,int t2i){
if(t2i == 0)
return 1;
if(t1i == 0)
return 0;
if(t1->arr[t1i].num != t2->arr[t2i].num)
return 0;
return compare(t1,t1->arr[t1i].lchild,t2,t2->arr[t2i].lchild)&&compare(t1,t1->arr[t1i].rchild,t2,t2->arr[t2i].rchild);
}
/**************************************************************
Problem: 1520
User: xhalo
Language: C
Result: Accepted
Time:10 ms
Memory:912 kb
****************************************************************/