剑指Offer

剑指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代码。

  1 // 652327    zhuli19901106    1520    Accepted    点击此处查看所有case的执行结果    1048KB    2486B    10MS
  2 // 201311162044
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 const int MAXN = 1005;
  7 int a[MAXN][3];
  8 int b[MAXN][3];
  9 int c[MAXN];
 10 int na, nb;
 11 int ra, rb;
 12 
 13 bool is_subtree(const int a[][3], const int b[][3], int ia, int ib)
 14 {
 15     if(a == NULL || b == NULL){
 16         return false;
 17     }
 18     if(ia < 0 || ia > na - 1){
 19         return false;
 20     }
 21     if(ib < 0 || ib > nb - 1){
 22         return false;
 23     }
 24     
 25     if(a[ia][0] == b[ib][0]){
 26         bool ret1, ret2;
 27         
 28         if(b[ib][1] != -1){
 29             ret1 = is_subtree(a, b, a[ia][1], b[ib][1]);
 30         }else{
 31             ret1 = true;
 32         }
 33 
 34         if(b[ib][2] != -1){
 35             ret2 = is_subtree(a, b, a[ia][2], b[ib][2]);
 36         }else{
 37             ret2 = true;
 38         }
 39         
 40         return (ret1 && ret2);
 41     }else{
 42         return false;
 43     }
 44 }
 45 
 46 int main()
 47 {
 48     int i, j;
 49     int x, y;
 50     
 51     while(scanf("%d%d", &na, &nb) == 2){
 52         for(i = 0; i < na; ++i){
 53             for(j = 0; j < 3; ++j){
 54                 a[i][j] = -1;
 55             }
 56         }
 57         for(i = 0; i < nb; ++i){
 58             for(j = 0; j < 3; ++j){
 59                 b[i][j] = -1;
 60             }
 61         }
 62         
 63         for(i = 0; i < na; ++i){
 64             scanf("%d", &x);
 65             a[i][0] = x;
 66             c[i] = 0;
 67         }
 68         for(i = 0; i < na; ++i){
 69             scanf("%d", &j);
 70             if(j == 1){
 71                 scanf("%d", &x);
 72                 a[i][1] = x - 1;
 73                 ++c[x - 1];
 74             }else if(j == 2){
 75                 scanf("%d%d", &x, &y);
 76                 a[i][1] = x - 1;
 77                 a[i][2] = y - 1;
 78                 ++c[x - 1];
 79                 ++c[y - 1];
 80             }
 81         }
 82         ra = -1;
 83         for(i = 0; i < na; ++i){
 84             if(c[i] == 0){
 85                 ra = i;
 86             }
 87         }
 88 
 89         for(i = 0; i < nb; ++i){
 90             scanf("%d", &x);
 91             b[i][0] = x;
 92             c[i] = 0;
 93         }
 94         for(i = 0; i < nb; ++i){
 95             scanf("%d", &j);
 96             if(j == 1){
 97                 scanf("%d", &x);
 98                 b[i][1] = x - 1;
 99                 ++c[x - 1];
100             }else if(j == 2){
101                 scanf("%d%d", &x, &y);
102                 b[i][1] = x - 1;
103                 b[i][2] = y - 1;
104                 ++c[x - 1];
105                 ++c[y - 1];
106             }
107         }
108         rb = -1;
109         for(i = 0; i < nb; ++i){
110             if(c[i] == 0){
111                 rb = i;
112             }
113         }
114         
115         // you can't put this if() up front, if na > 0 && nb == 0, then the input data for a is ignored
116         if(na <= 0 || nb <= 0){
117             printf("NO
");
118             continue;
119         }
120         
121         if(ra == -1 || rb == -1){
122             // there is at least one invalid tree
123             printf("NO
");
124             continue;
125         }
126         
127         for(i = 0; i < na; ++i){
128             if(is_subtree(a, b, i, rb)){
129                 break;
130             }
131         }
132         if(i < na){
133             printf("YES
");
134         }else{
135             printf("NO
");
136         }
137     }
138     
139     return 0;
140 }