输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

// test20.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include<iostream>

#include<vector>

#include<string>

#include<queue>

#include<stack>

using namespace std;

struct TreeNode {

	int val;

	struct TreeNode *left;

	struct TreeNode *right;

	TreeNode(int x) :

	val(x), left(NULL), right(NULL) {

	}

};

class Solution {

public:

	//1.先在二叉树tree1中找到tree2的根节点

	//2.在判断tree2的左右孩子是否在tree1中

	//3.如果不存在继续遍历tree1的左孩子和右孩子

	bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)

	{

		if (pRoot1 == NULL) return false;//这一点很重要，要不然if (pRoot1->val == pRoot2->val)会报空指针的错误

		if (pRoot2 == NULL) return false;

		bool result = false;

		if (pRoot1->val == pRoot2->val)

		{

			result = DoseTree1HasTree2(pRoot1,pRoot2);

		}

		if (result == false)

			result = HasSubtree(pRoot1->left,pRoot2);

		if (result == false)

			result = HasSubtree(pRoot1->right,pRoot2);

		return result;

	}

	//如果tree1为空，返回false;如果tree2为空，返回true；如果两者都不为空，继续判断其左右孩子

	bool DoseTree1HasTree2(TreeNode* tree1, TreeNode* tree2)

	{

		if (tree1 == NULL &&tree2 == NULL) return true;//tree1和tree2都为空

		else if (tree1 == NULL && tree2!=NULL) return false;

		else if (tree1 != NULL && tree2==NULL) return true;

		else

		{

			if (tree1->val != tree2->val) return false;

			return DoseTree1HasTree2(tree1->left, tree2->left) && DoseTree1HasTree2(tree1->right, tree2->right);

		}

	}

	void preCreate(TreeNode* &T)

	{

		int num;

		cin >> num;

		if (num == 0) T = NULL;

		else

		{

			T = new TreeNode(num);

			preCreate(T->left);

			preCreate(T->right);

		}

	}

	void preOrder(TreeNode* T)

	{

		if (T == NULL) return;

		else

		{

			cout << T->val << "  ";

			preOrder(T->left);

			preOrder(T->right);

		}

	}

};

int main()

{

	Solution so;

	TreeNode *T1;

	TreeNode *T2;

	vector<int> pre = { 1,2,4,7,3,5,6,8 };

	vector<int> in = { 4,7,2,1,5,3,8,6 };

	cout << "创建T1:" << endl;

	so.preCreate(T1);

	cout << "创建T1成功！" << endl;

	cout << "创建T2:" << endl;

	so.preCreate(T2);

	cout << "创建T2成功！" << endl;

	cout << "T1的前序遍历:" << endl;

	so.preOrder(T1);

	cout << endl;

	//cout << "T2的前序遍历:" << endl;

	//so.preOrder(T2);

	//cout << endl;

	cout << "T2是不是T1的子树：" << endl;

	bool result = so.HasSubtree(T1,T2);

	cout << result << endl;

	cout << endl;

	return 0;

}

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）的相关教程结束。