剑指OFFER之树的子结构(九度OJ1520)

题目描述:

输入两颗二叉树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
****************************************************************/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xcywt

编译到底做了什么(***.c -> ***.o的过程)

 (第一次写博客,好激动的说.......) 我们知道,一个程序由源代码到可执行文件往往由这几步构成: 预处理(Prepressing)-> 编译(Compil...

20850
来自专栏企鹅号快讯

Python教学从零开始——第四天

在前面的几天中,我们了解了tulpe,list的操作,os模块案例,for循环,前面的示例比较简单,几乎没有太多的语法,今天我们要来说一法语法,语法通常都是硬性...

23770
来自专栏漫漫深度学习路

tensorflow:AToolDeveloperGuideToTFModelFIles

Tensorflow Model Files 最近闲来无聊,想深入理解一下tensorlfow,也不知从何下手,突然间发现了官方文档的Extend模块下还有这个...

38150
来自专栏HansBug's Lab

1293: [SCOI2009]生日礼物

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1096  Solv...

28470
来自专栏一“技”之长

一个移动开发者的Mock数据之路 原

    在前端开发中,很大一部分工作都是将后台数据获取到后展示在前端界面上。如果接口是现成的,这个过程还相对容易一些,但是如果接口的开发和前端开发是同时进行的,...

7710
来自专栏深度学习之tensorflow实战篇

把一个矩阵行优先展成一个向量,numpy.ravel() vs numpy.flatten()区别

首先声明两者所要实现的功能是一致的(将多维数组降位一维),两者的区别在于返回拷贝(copy)还是返回视图(view),numpy.flatten()返回一份拷贝...

35660
来自专栏计算机视觉与深度学习基础

本次新生赛部分题解

A poj1129 这题的愿意是考察四色原理(不是太难,主要是了解),但是模拟+暴力枚举也是可以过的,有几个WA点,注意看注释 #include<cstdio>...

22050
来自专栏magicsoar

Effective Modern C++翻译(5)-条款4:了解如何观察推导出的类型

条款4:了解如何观察推导出的类型 那些想要知道编译器推导出的类型的人通常分为两种,第一种是实用主义者,他们的动力通常来自于软件产生的问题(例如他们还在调试解决中...

21180
来自专栏Web 开发

做wordpress CMS必须用到的强力代码(转)

这个代码很强力,做一个wordpress cms的索引页面(index.php) 这个代码是必须要会使用,不然会走很多弯路。

11320
来自专栏数值分析与有限元编程

fortran知识 | 代码错误(domain error)

如图所示,提示为:domain error ? 这表示数学函数错误,如超出数学函数的定义域,负数开平方,分母为0等等;也有可能是浮点数错误,比如sqrt(4),...

37960

扫码关注云+社区

领取腾讯云代金券