转载请注明出处：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 =http://www.mamicode.com/= pTree2[index2].data)>
/**************************************************************
    Problem: 1520
    User: mmc_maodun
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:912 kb
****************************************************************/