#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define N 10000000
struct BTNode{
char data;
BTNode *
lchild;
BTNode *
rchild;
}BTNode;
char IN[N],POST[N];
struct BTNode *nil=
NULL;
struct BTNode *CreatTree(
char IN[],
char POST[],
int l1,
int r1,
int l2,
int r2)
{
if(l1>
r1)
{
return nil;
}
struct BTNode *T=(
struct BTNode *)malloc(
sizeof(BTNode));
T->lchild=nil; T->rchild=
nil;
T->data=
POST[r2];
int i;
for(i=l1;i<=r1;i++
)
{
if(IN[i]==
POST[r2])
break;
}
T->lchild=CreatTree(IN, POST, l1, i-
1, l2, l2+i-
1-
l1);
T->rchild=CreatTree(IN, POST, i+
1, r1, l1+i-l2, r1-
1);
return T;
}
int main()
{
int n;
scanf("%d",&
n);
for(
int i=
1;i<=n;i++
)
cin>>
IN[i];
for(
int i=
1;i<=n;i++
)
cin>>
POST[i];
CreatTree(IN,POST,1,n,
1,n);
return 0;
}
转载于:https://www.cnblogs.com/2014slx/p/11341079.html
