百度笔试题：判断一个二叉树是否是另一颗二叉树的子树

是返回1，否则返回-1

给出了函数体

int IsSubTree(BiTree* root1, BiTree* root2)//判断root2是否是root1的子树

{

//写自己的代码

}

思想：首先找到root1中和root2根节点相等的节点，再从该节点开始比较是否每个节点都相等

#include<iostream>
using namespace std;
typedef struct BiTree
{
int value;
BiTree *left, *right;
}BiNode, *MyBiTree;

void createBiTree(MyBiTree &T)
{
int data;
cin >> data;
if (-1 == data)//输入结束标志
T = NULL;
else
{
T = new BiNode;//分配新的内存
T->value = data;//输入的值赋值给数的节点值
createBiTree(T->left);//递归创建左子树
createBiTree(T->right);//递归创建右子树
}
}

void deleteBiTree(MyBiTree &T)
{
if (T != NULL)//树不为空就递归删除左子树，递归删除右子树，再最后释放根节点内存
{
deleteBiTree(T->left);
deleteBiTree(T->right);
delete T;
}
}

int IsSubTreeSameRootValue(BiTree *root1,BiTree *root2)//两棵树的起始节点的值已经相等，在判断其他节点是否相等
{
if (NULL == root2)
return 1;
if (NULL == root1)
return -1;
if (root1->value != root2->value)
return -1;
int i = IsSubTreeSameRootValue(root1->left, root2->left);//根节点已经相等，判断左孩子
int j = IsSubTreeSameRootValue(root1->right, root2->right);//根节点已经相等，判断右孩子
if (1 == i && 1 == j)//如果左右孩子都相等，则是子树，否则不是
return 1;
else
return -1;
}

int IsSubTree(BiTree* root1, BiTree* root2)//判断root2是否是root1的子树
{
if (NULL == root2)//空树是任何树的子树
return 1;
if (NULL == root1)//如果root2不为空，而root1为空，则不是
return -1;
if (root1->value == root2->value)//如果两个树都不为空，且根节点值相等
return IsSubTreeSameRootValue(root1, root2);//从相等的节点开始判断是否是子树
int i = IsSubTree(root1->left, root2);//如果节点值不相等，看root1的左子树是中是否含有该子树
if (1 == i)
return 1;
else
return IsSubTree(root1->right, root2);//如果节点值不等，并且左子树中没有该子树，再看其右子树中是否含有该子树
}
int main()
{
MyBiTree root1, root2;
createBiTree(root1);
createBiTree(root2);
cout<<IsSubTree(root1, root2);
delete(root1);
delete(root2);
system("pause");
return 0;
}