# 1284. Tree Recovery

### 前序中序求后序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#define ll long long

using namespace std;

string pre, in, post;
int len;

void postorder(int lpre, int rpre, int lin, int rin) {
if (lpre > rpre || lin > rin) return ;
int rootin = lin;
while (in[rootin] != pre[lpre] && rootin < pre.size()) rootin++;
int left = rootin - lin;
postorder(lpre + 1, lpre + left, lin, rootin - 1);
postorder(lpre + left + 1, rpre, rootin + 1, rin);
post.push_back(pre[lpre]);
}

int main() {
while (cin >> pre >> in) {
post.clear();
len = in.length();
postorder(0, len - 1, 0, len - 1);
cout << post << "\n";
}
return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
char data;
struct Node *lchild;
struct Node *rchild;
}Node;
typedef Node* node;
Node* create_first(string pre,string middle,int n)//已知前序序列和中序序列
{
Node *root;
if(n<=0) return NULL;
else{
root =new Node;int pos=0;
for(int i=0;i<n;i++){
if(middle[i]==pre[0]) {
pos=i;break;
}
}
root->data=middle[pos];
string s1=pre.substr(1,pos);
string s2=middle.substr(0,pos);
root->lchild=create_first(s1,s2,pos);
string s3=pre.substr(pos+1,n-pos-1);
string s4=middle.substr(pos+1,n-pos-1);
root->rchild=create_first(s3,s4,n-pos-1);
return root;
}
}
int getnode(Node *T)
{
if(T==NULL) return 0;
else{
return 1+getnode(T->lchild)+getnode(T->rchild);
}
}
void bfs(node root)
{
if(root){
bfs(root->lchild);
bfs(root->rchild);
cout<<root->data;
}
}
int main()
{
string pre,middle;
while(cin>>pre>>middle){