剑指Offer - 九度1520 - 树的子结构

剑指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 ;

 }

巴特西

剑指Offer - 九度1520 - 树的子结构

最新文章

热门文章