【剣指Offer面接プログラミング問題】テーマ1520:木のサブ構造--九度OJ

タイトルの説明:
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

【解題の考え方】木を見ると、第一の考え方は再帰であり、再帰の効率は確かに高くないが、OJでは時間効率にこだわり、適切な剪定に合わせてACを速くすることがある.本題は2層の再帰が必要で、まずAツリーのどのサブツリーがBツリーと比較するかを確定し、つまりAツリーのサブノードを確定し、これは第1層の再帰である.また,比較の際にもツリーの再帰を用いて,各ノードを比較する必要がある.2層の再帰の順序は,いずれも木の先順が遍歴する順序である.
中間には少しのテクニックがありますが、第1層の再帰では、Bツリーがサブツリーであることを決定するときに、再帰を断固として停止し、過剰な反復を避けなければなりません.
AC code:

#include 
#include 
using namespace std;
 
struct st
{
  int val;
  st *lc;
  st *rc;
};
bool flg=false,reflg=false;
 
void check(st *s1,st*s2)
{
  if(s1->val!=s2->val)
  {
    flg=true;
    return ;
  }
  if(s2->lc==NULL && s2->rc==NULL)
    return ;
  if(s1->lc!=NULL && s2->lc!=NULL)
    check(s1->lc,s2->lc);
  else if(s1->rc!=NULL && s2->rc!=NULL)
    check(s1->rc,s2->rc);
  else
  {
    flg=true;
    return ;
  }
}
 
void fill(vector &veca,const int&n)
{
  st ss;
  ss.val=0;
  ss.lc=ss.rc=NULL;
  veca.push_back(ss);
  for(int i=0;ilc && flg)
    chk(st1->lc,st2);
  if(st1->rc && flg)
    chk(st1->rc,st2);
}
 
int main()
{
  int n,m;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    vector veca,vecb;
    fill(veca,n);
    fill(vecb,m);
    st* st1=&veca[1],*st2=&vecb[1];
    flg=false;
    if(!st2)flg=false;
    else chk(st1,st2);
    if(flg)
      printf("NO
");
    else
      printf("YES
");
  }
  return 0;
}
/**************************************************************
    Problem: 1520
    User: huo_yao
    Language: C++
    Result: Accepted
    Time:10 ms
    Memory:1024 kb
****************************************************************/

タイトルリンク:http://ac.jobdu.com/problem.php?pid=1520
九度-剣指Offer練習問題全套解答ダウンロード:http://download.csdn.net/detail/huoyaotl123/8276299