[problem description]

Suppose the binary tree is stored in the form of binary list, root points to the root node, p and q are two different nodes in the binary tree, and they are not the points on the path from the root to the node, so we can program and solve the common ancestor which is closest to them.
[input form]

The first and middle order traversal sequences of the binary tree are used to create the chain storage structure of the binary tree, and the two node data x and y of the binary tree

[output form]

The nearest common ancestor whose node data value is x and y, if there is no common ancestor, NULL will be output
[sample input]

GABDCEF

BDAEFCG

DF

[sample output]

A

#include<iostream>
#include<stdlib.h>
#include<cstring>
using namespace std;

struct BiTNode
{
	char data;
	BiTNode *LChild;
	BiTNode *RChild;
};

BiTNode *Create(char *pre,char *mid,int len)
{
	if(len==0)
	return NULL;
	int i;
	BiTNode *p;
	p=(BiTNode*)malloc(sizeof(BiTNode));
	p->data=pre[0];
	for(i=0;i<len;i++)
	{
		if(pre[0]==mid[i])
		break;
	}
	p->LChild=Create(pre+1,mid,i);
	p->RChild=Create(pre+i+1,mid+i+1,len-i-1);
	return p;
}

void Search(BiTNode *T,BiTNode *node)
{
	if(T!=NULL)
	{
		if(T->data==node->data)
		node=T;
		Search(T->LChild,node);
		Search(T->RChild,node);
	}
}

BiTNode *search(BiTNode *T,BiTNode *node1,BiTNode *node2)
{
	if(T==NULL)
	return NULL;
	if(T->data==node1->data||T->data==node2->data)
	return T;
	BiTNode *left=search(T->LChild,node1,node2);
	BiTNode *right=search(T->RChild,node1,node2);
	if(left&&right)
	return T;
	if(left)
	return left;
	if(right)
	return right;
	return NULL;
}

BiTNode *GetParent(BiTNode *T,BiTNode *node1,BiTNode *node2)
{
	BiTNode *p=search(T,node1,node2);
	return p;
}

int main()
{
	int len;
	char pre[100],mid[100];
	char a,b;
	BiTNode *T=NULL;
	BiTNode *node1=NULL,*node2=NULL,*node=NULL;
	node1=(BiTNode*)malloc(sizeof(BiTNode));
	node2=(BiTNode*)malloc(sizeof(BiTNode));
	node=(BiTNode*)malloc(sizeof(BiTNode));
	cin>>pre;
	cin>>mid;
	len=strlen(pre);
	T=Create(pre,mid,len);
	cin>>a>>b;
	node1->data=a;
	node2->data=b;
	Search(T,node1);
	Search(T,node2);
	node=GetParent(T,node1,node2);
	if(node!=NULL&&node->data!=T->data)
	cout<<node->data;
	else
	cout<<"NULL";
}