学步园

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

const int maxn = 100;
struct Node{
    int data;
    Node *lchild, *rchild, *parent;
};
Node node[maxn];
int cnt;

void init(){
    memset(node, '\0', sizeof(node));
    cnt = 0;
}
void create_minimal_tree(Node* &head, Node *parent, int a[], int start, int end)
{
    if(start <= end){
        int mid = (start + end)>>1;
        node[cnt].data = a[mid];
        node[cnt].parent = parent;
        head = &node[cnt++];
        create_minimal_tree(head->lchild, head, a, start, mid-1);
        create_minimal_tree(head->rchild, head, a, mid+1, end);
    }
}

Node* findRoot(Node *r1, Node *r2_root)
{
	if(r1 == NULL)
		return NULL;
	if(r1->data == r2_root->data)
		return r1;
	Node *re1, *re2, *re = NULL;

	re1 = findRoot(r1->lchild, r2_root);
	if(re1 != NULL)
		re = re1;
	re2 = findRoot(r1->rchild, r2_root);
	if(re2 != NULL)
		re = re2;
	return re;
}

bool compareTree(Node *root, Node *r2)
{
	if(root == NULL && r2 == NULL)
		return true;
	if(root == NULL || r2 == NULL)
		return false;		
	if(root->data != r2->data)
		return false;
	return compareTree(root->lchild, r2->lchild) && compareTree(root->rchild, r2->rchild);
}

bool contain_tree(Node* &r1, Node* &r2)
{
	Node *root = findRoot(r1, r2);
	return compareTree(root, r2);
}

int main(){
    init();
    int a1[] = {
        0, 1, 2, 3, 4, 5, 6
    };
    int a2[] = {
        0, 1, 2
    };
    Node *r1 = NULL, *r2 = NULL;
    create_minimal_tree(r1, NULL, a1, 0, 6);
    create_minimal_tree(r2, NULL, a2, 0, 2);
    if(contain_tree(r1, r2))
        cout<<"tree r1 contains r2"<<endl;
    else cout<<"tree r1 does not contaions r2"<<endl;
    return 0;
}