题目描述：

输入两颗二叉树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 38 8 7 9 2 4 72 2 32 4 5002 6 7008 9 22 2 3001 12030

样例输出：

YESNO

提示：

B为空树时不是任何树的子树。

 

Code:

#include <cstdio> using namespace std; struct BinaryTreeNode{    int data;    int lchild;    int rchild;}; bool DoesTree1HaveTree2(BinaryTreeNode *arr1,int root1,BinaryTreeNode *arr2,int root2){    if(root2==0)        return true;    if(root1==0)        return false;    if(arr1[root1].data!=arr2[root2].data)        return false;    return DoesTree1HaveTree2(arr1,arr1[root1].lchild,arr2,arr2[root2].lchild)&&
　　　　　　　　　　　　　　DoesTree1HaveTree2(arr1,arr1[root1].rchild,arr2,arr2[root2].rchild);} bool HasSubtree(BinaryTreeNode *arr1,int root1,BinaryTreeNode *arr2,int root2){    bool result=false;    if(root1!=0&&root2!=0){        if(arr1[root1].data=http://www.mamicode.com/=arr2[root2].data){            result=DoesTree1HaveTree2(arr1,root1,arr2,root2);        }        if(!result){            result=HasSubtree(arr1,arr1[root1].lchild,arr2,root2);        }        if(!result){            result=HasSubtree(arr1,arr1[root1].rchild,arr2,root2);        }    }    return result;} int main(){    int n,m;    while(scanf("%d%d",&n,&m)!=EOF){        BinaryTreeNode arr1[1010],arr2[1010];        for(int index1=1;index1<=n;++index1){            scanf("%d",&arr1[index1].data);        }        for(int cnt1=1;cnt1<=n;++cnt1){            int numberOfChild;            scanf("%d",&numberOfChild);            if(numberOfChild==2){                scanf("%d%d",&arr1[cnt1].lchild,&arr1[cnt1].rchild);            }else{                if(numberOfChild==1){                    scanf("%d",&arr1[cnt1].lchild);                    arr1[cnt1].rchild=0;                }else{                    arr1[cnt1].lchild=arr1[cnt1].rchild=0;                }            }        }        for(int index2=1;index2<=m;++index2){            scanf("%d",&arr2[index2].data);        }        for(int cnt2=1;cnt2<=m;++cnt2){            int numberOfChild;            scanf("%d",&numberOfChild);            if(numberOfChild==2){                scanf("%d%d",&arr2[cnt2].lchild,&arr2[cnt2].rchild);            }else{                if(numberOfChild==1){                    scanf("%d",&arr2[cnt2].lchild);                    arr2[cnt2].rchild=0;                }else{                    arr2[cnt2].lchild=arr2[cnt2].rchild=0;                }            }        }        if(n==0||m==0||n<m){            printf("NO\n");            continue;        }        bool ans=HasSubtree(arr1,1,arr2,1);        if(ans==true)            printf("YES\n");        else            printf("NO\n");    }    return 0;} /**************************************************************    Problem: 1520    User: lcyvino    Language: C++    Result: Accepted    Time:10 ms    Memory:1020 kb****************************************************************/

 

剑指OFFER之树的子结构