#include <iostream>
#include <vector>
using namespace std;

struct TreeNode{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x):
		val(x), left(NULL), right(NULL){}
};

void preVist(TreeNode* pRoot,vector<int> &vec){
	if(pRoot!=NULL){
		vec.push_back(pRoot->val);
		preVist(pRoot->left,vec);
		preVist(pRoot->right,vec);
	}
}

void inVist(TreeNode* pRoot,vector<int> &vec){
	if(pRoot!=NULL){
		inVist(pRoot->left,vec);
		vec.push_back(pRoot->val);
		inVist(pRoot->right,vec);
	}
}

bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){
	if(pRoot1==NULL||pRoot2==NULL)
		return 0;
	else{
	vector<int> pre1,in1;
	preVist(pRoot1,pre1);
	inVist(pRoot1,in1);

	vector<int> pre2,in2;
	preVist(pRoot2,pre2);
	inVist(pRoot2,in2);

	int c=0;
	int lenp1=pre1.size();
	int lenp2=pre2.size();
	bool m1=false;
	for(int i=0;i<lenp1;i++){
		if(pre1[i]==pre2[c]){
			if(c==lenp2-1){
				m1=true;
				break;
			}else
				c++;
		}
	}

	int leni1=in1.size();
	int leni2=in2.size();
	bool m2=false;
	c=0;
	for(int i=0;i<leni1;i++){
		if(in1[i]==in2[c]){
			if(c==leni2-1){
				m2=true;
				break;
			}else
				c++;
		}
	}
	
	if(m1==true&&m2==true)
		return 1;
	else
		return 0;
	}
}

void printTree(TreeNode *T){
	if(T!=NULL){
		cout<<T->val<<" ";
		printTree(T->left);
		printTree(T->right);
	}
}

int main(){
	TreeNode t1(1),t2(2),t3(3),t4(4),t5(5),t6(6);
	t1.left=&t2;
	t1.right=&t3;
	t2.left=&t4;
	t2.right=&t5;
	t3.left=&t6;
	TreeNode *pRoot1=&t1;
	
	TreeNode T1(1),T2(3);
	T1.right=&T2;
	TreeNode *pRoot2=&T1;

	cout<<HasSubtree(pRoot1,pRoot2)<<endl;
	system("pause");
}