转载请注明出处：http://blog.csdn.net/ns_code/article/details/25907685

剑指offer第18题，九度OJ上測试通过！

题目描写叙述：

输入两颗二叉树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为空树时不是不论什么树的子树

在写这道题目时。卡在了測试代码上，这个题目的測试代码有点繁杂，最后參考了一哥的文章。改用数组作为存储二叉树节点的数据结构，果然写測试代码方便了非常多。

另外，程序中有一些要注意的地方。在程序中表明了凝视。

AC代码：

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

typedef struct BTNode

{

	int data;

	int rchild;

	int lchild;

}BTNode;

/*

推断pTree2是否是与pTree1有共同的根节点的pTree1子树

*/

bool isSubTree(BTNode *pTree1,int index1,BTNode *pTree2,int index2)

{

	//前两个if语句不能颠倒。不然当pTree1和pTree2同样时，会误判为false

	if(index2 == -1)

		return true;

	if(index1 == -1)

		return false;

	if(pTree1[index1].data != pTree2[index2].data)

		return false;

	else

		return isSubTree(pTree1,pTree1[index1].lchild,pTree2,pTree2[index2].lchild) &&

			   isSubTree(pTree1,pTree1[index1].rchild,pTree2,pTree2[index2].rchild);

}

/*

推断pTree1是否包括pTree2

*/

bool isContainTree(BTNode *pTree1,int index1,BTNode *pTree2,int index2)

{

	if(pTree1==NULL || pTree2==NULL)

		return false;

	if(index1==-1 || index2==-1)

		return false;

	bool result = false;

	if(pTree1[index1].data == pTree2[index2].data)

		result = isSubTree(pTree1,index1,pTree2,index2);

	//假设pTree1[index1].lchild为-1。下次递归时会通过index1==-1的推断返回false，

	//因此这里不须要再加上pTree1[index1].lchild!=-1的推断条件

	if(!result)

		result = isContainTree(pTree1,pTree1[index1].lchild,pTree2,index2);

	if(!result)

		result = isContainTree(pTree1,pTree1[index1].rchild,pTree2,index2);

	return result;

}

int main()

{

	int n,m;

	while(scanf("%d %d",&n,&m) != EOF)

	{

		//输入树pTree1各节点的值

		BTNode *pTree1 = NULL;

		if(n>0)

		{

			pTree1 = (BTNode *)malloc(n*sizeof(BTNode));

			if(pTree1 == NULL)

				exit(EXIT_FAILURE);

			int i,data;

			//输入n个节点的data

			for(i=0;i<n;i++)

			{

				scanf("%d",&data);

				pTree1[i].data = data;

				pTree1[i].rchild = -1;

				pTree1[i].lchild = -1;

			}

			//输入n行节点连接关系

			for(i=0;i<n;i++)

			{

				int ki;

				scanf("%d",&ki);

				if(ki == 0)

					continue;

				else if(ki == 1)

				{

					int lindex;

					scanf("%d",&lindex);

					pTree1[i].lchild = lindex-1;

				}

				else

				{

					int lindex,rindex;

					scanf("%d",&lindex);

					scanf("%d",&rindex);

					pTree1[i].lchild = lindex-1;

					pTree1[i].rchild = rindex-1;

				}

			}

		}

		//输入树pTree2各节点的值

		BTNode *pTree2 = NULL;

		if(m>0)

		{

			pTree2 = (BTNode *)malloc(m*sizeof(BTNode));

			if(pTree2 == NULL)

				exit(EXIT_FAILURE);

			int i,data;

			//输入n个节点的data

			for(i=0;i<m;i++)

			{

				scanf("%d",&data);

				pTree2[i].data = data;

				pTree2[i].rchild = -1;

				pTree2[i].lchild = -1;

			}

			//输入n行节点连接关系

			for(i=0;i<m;i++)

			{

				int ki;

				scanf("%d",&ki);

				if(ki == 0)

					continue;

				else if(ki == 1)

				{

					int lindex;

					scanf("%d",&lindex);

					pTree2[i].lchild = lindex-1;

				}

				else

				{

					int lindex,rindex;

					scanf("%d",&lindex);

					scanf("%d",&rindex);

					pTree2[i].lchild = lindex-1;

					pTree2[i].rchild = rindex-1;

				}

			}

		}

		if(isContainTree(pTree1,0,pTree2,0))

			printf("YES\n");

		else

			printf("NO\n");

	}

	return 0;

}