首页 > 代码库 > 剑指OFFER之树的子结构（九度OJ1520）

剑指OFFER之树的子结构（九度OJ1520）

2024-07-07 01:07:12   229人阅读

题目描述：

输入两颗二叉树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为空树时不是任何树的子树。

解题思路：

　　这道题有个坑，首先题目要求n与m的范围不能为0，但是测试用例中第三个和第四个有可能分别是第一个树空和第二个数空的特殊情况。因此，要特别注意这里，在scanf("%d %d",&n,&m)的时候对mn注意限制的范围。

　　另外用例并没有给出单个叶子的情况，这时注意，当输入为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\n");
        else
            printf("NO\n");
    }
    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
****************************************************************/

 


联系
我们