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){
        node head=create_first(pre,middle,pre.length());
        bfs(head);
        cout<<endl;
        //cout<<getnode(head);
    }
}