Problem D

#include<iostream>
#include<string>
using namespace std;
typedef struct Node
{
    Node * lchild,* rchild;
    char data;
    Node(char c)
    {
        lchild = rchild = NULL;
        data = c;
    }
}*BTree;

Node * creat(string s1,string s2)//根据先序和中序建树
{
    if(s1.size() == 0)
        return NULL;
    char c = s1[0];
    Node * root = new Node(c);
    int pivot = s2.find(c);//pivot为截取长度
    root->lchild = creat(s1.substr(1,pivot),s2.substr(0,pivot));
    root->rchild = creat(s1.substr(pivot + 1),s2.substr(pivot + 1));
    return root;
}

void postOrder(BTree root)
{
    if(!root)
        return;
    postOrder(root->lchild);
    postOrder(root->rchild);
    cout << root->data;
}

int main(void)
{
    string s1,s2;
    
    while(cin >> s1 >> s2)
    {
        BTree root = creat(s1, s2);
        postOrder(root);
        cout << endl;
    }
    return 0;
}

/*
*递归建树 ， 后序遍历。
*/

#include<bits/stdc++.h> 

using namespace std;

struct Node
{
    char v;
    struct Node* lchild,* rchild;
};

string spre, smid;

Node* Create(int preL, int preR, int inL, int inR)
{
    if(preL > preR) return nullptr;
    Node* root = new Node;
    root->v = spre[preL];
    int k = smid.find(spre[preL]);
    int leftNum = k - inL;
    root->lchild = Create(preL+1, preL+leftNum, inL, k-1);
    root->rchild = Create(preL+leftNum+1, preR, k+1, inR);
    return root;
}

void LastOrder(Node* root)
{
    if(root == nullptr) return ;
    LastOrder(root->lchild);
    LastOrder(root->rchild);
    cout << root->v;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> spre >> smid)
    {
        LastOrder(Create(0, spre.length()-1, 0, smid.length()-1));
        cout << "\n";
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//递归求解
void postOrder(string s1,string s2)
{
    if(!s1.size()) return;
    int root  = s2.find(s1[0]);
    postOrder(s1.substr(1,root),s2.substr(0,root));
    postOrder(s1.substr(root+1),s2.substr(root+1));
    cout<<s1[0];
}
int main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        postOrder(s1,s2);
        cout<<endl;
    }
    return 0;
}

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

struct TreeNode {
    char data;              //数据
    TreeNode* leftChild;    //左子树
    TreeNode* rightChild;   //右子树
    TreeNode(char c): data(c) {}
};

//根据先序序列preOrder和中序序列inOrder，构造二叉树，返回根结点（指针）
TreeNode* Build(string preOrder, string inOrder) {
    if (preOrder.size() == 0) {
        return nullptr;             //返回空树
    }
    char c = preOrder[0];           //当前字符
    auto* root = new TreeNode(c);   //创建新结点
    int position = inOrder.find(c); //寻找切分点
    root->leftChild = Build(preOrder.substr(1, position),
                            inOrder.substr(0, position));   //构造左子树
    root->rightChild = Build(preOrder.substr(position + 1),
                             inOrder.substr(position + 1)); //构造右子树
    return root;
}

void PostOrder(TreeNode* root) {    //后序遍历
    if (root == nullptr) {
        return;
    }
    PostOrder(root->leftChild);
    PostOrder(root->rightChild);
    cout << root->data;
}

int main() {
    string preOrder, inOrder;
    while (cin >> preOrder >> inOrder) {
        TreeNode* root = Build(preOrder, inOrder);
        PostOrder(root);
        cout << endl;
    }
    return 0;
}

// 递归。写过好多次了
#include<iostream>
#include<string>
using namespace std;

typedef struct Tree{
    char ch;
    Tree* lchild;
    Tree* rchild;
    Tree(char ch):ch(ch){}
}Tree;

// 建树
Tree* build(string prior, string inorder){
    if(prior.length()==0) return NULL;
    char ch = prior[0];
    Tree* root = new Tree(ch);
    int index = inorder.find(ch);
    root->lchild = build(prior.substr(1,index),inorder.substr(0,index));
    root->rchild = build(prior.substr(index+1),inorder.substr(index+1));
    return root;
}
// 后序遍历
void postorder(Tree* root){
    if(root==NULL) return;
    postorder(root->lchild);
    postorder(root->rchild);
    cout<<root->ch;
}

int main(){
    string prior,inorder;
    while(cin>>prior>>inorder){
        Tree* root = build(prior,inorder);
        postorder(root);
        cout<<endl;
    }
    return 0;
}

#include<cstring>
(803)#include<iostream>
using namespace std;

struct Tree {
    char val;
    Tree *left, *right;
    
    Tree(char val) {
        this->val=val;
        this->left=NULL;
        this->right=NULL;
    }
};


Tree* buildTree(string preOrder, string inOrder, int preStart, int preEnd, int inStart, int inEnd) {
    if(preStart>preEnd) return NULL;
    Tree *root=new Tree(preOrder[preStart]);
    int mid=0;
    for(int i=inStart; i<=inEnd; ++i) 
        if(inOrder[i]==preOrder[preStart]) break;
        else ++mid;
    root->left=buildTree(preOrder, inOrder, preStart+1, preStart+mid, inStart, inStart+mid-1);
    root->right=buildTree(preOrder, inOrder, preStart+mid+1, preEnd, inStart+mid+1, inEnd);
    return root;
}

void postOrder(Tree *root) {
    if(root) {
        postOrder(root->left);
        postOrder(root->right);
        cout<<root->val;
    }
}


int main() {
    string preOrder, inOrder;
    while(cin>>preOrder>>inOrder) {
        int size=preOrder.size();
        Tree *root=buildTree(preOrder, inOrder, 0, size-1, 0, size-1);
        postOrder(root);
        cout<<endl;
    }
}

#include<stdio.h>
(737)#include<string.h>
char pre[100],order[100];
void help(int p_l,int p_r,int o_l,int&nbs***bsp;   if(p_l>p_r) return ;
    if(p_l==p_r)  {printf("%c",pre[p_l]);return ;}
    int x,l;
    for( x=o_l; x<=o_r; x++)
        if(order[x]==pre[p_l]) break;
    l=x-o_l;//左子树结点个数
    help(p_l+1,p_l+l,o_l,x-1);
    help(p_l+l+1,p_r,x+1,o_r);
    printf("%c",pre[p_l]);
    return ;
}
int main(){
    while(scanf("%s %s",pre,order)!=EOF){
        int len=strlen(pre);
        if(len==1) printf("%c",pre[0]);
        else help(0,len-1,0,len-1);
        printf("\n");
    }

    return 0;
}

include<iostream>
#include<string>
using namespace std;
string post="";
void fun(string pre,string in,int l1,int r1,int l2,int r2){
    if(l1<=r1){
        post = pre[l1]+post;
        int i=l2;
        while(i<=r2 && pre[l1]!=in[i]) i++;
        fun(pre,in,i-l2+l1+1,r1,i+1,r2);
        fun(pre,in,l1+1,i-l2+l1,l2,i-1);
    }
}
int main(){
    string pre;
    string in;
    while(cin>>pre>>in){
        fun(pre,in,0,pre.length()-1,0,in.length()-1);
        cout<<post<<endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

string func(string s1, string s2) {
    if (s1.empty()) {
        return "";
    } else if (s1.length() == 1) {
        return s1;
    } else {
        string left_xian, left_zhong, right_xian, right_zhong;
        unsigned long mid = s2.find(s1[0]);
        left_zhong = s2.substr(0, mid);
        right_zhong = s2.substr(mid + 1);

        left_xian = s1.substr(1, mid);
        right_xian = s1.substr(mid + 1);
        return func(left_xian, left_zhong) + func(right_xian, right_zhong) + s1[0];
    }
}

int main() {
//    freopen("/home/dong/CLionProjects/untitled/in.txt", "r", stdin);
    string s1, s2;
    while (cin >> s1 >> s2) {
        cout << func(s1, s2) << endl;
    }

    return 0;
}

#include <iostream>
#include <cstring>
#define maxn 500
using namespace std;
typedef struct BTNode{
    char data;
    struct BTNode *left;
    struct BTNode *right;
}BTNode,*BiTree;
void post_Order(BiTree T){
    if(T==NULL)
        return;
    post_Order(T->left);
    post_Order(T->right);
    cout<<T->data;
}
char pre[maxn],in[maxn];
BTNode * Create(int preA,int preB,int inA,int inB){
    if(preA>preB) return NULL;
    BTNode * root = new BTNode;
    root->data = pre[preA];
    int k;
    for(k=inA;k<=inB;++k){
        if(in[k]==pre[preA])
            break;
    }
    int left_len = k - inA;
    root->left = Create(preA+1,preA+left_len,inA,k-1);
    root->right = Create(preA+left_len+1,preB,k+1,inB);
    return root;
}
int main(){
    gets(pre);
    gets(in);
    int len = strlen(pre);
    BiTree T;
    T = Create(0,len-1,0,len-1);
    post_Order(T);
    return 0;
}

#include<iostream>
#include<string>

using namespace std;

struct node
{
    char value;
    node* lchild;
    node* rchild;
    node(char ch)
    {
        value = ch;
        lchild = rchild = NULL;
    }
};

//根据先序遍历和中序遍历构建二叉树
//返回当前子树的根节点
node* buildTree(string pre, string in)
{
    int len = pre.size();    //pre和in的长度始终是相同的
    if(len<=0) return NULL;
    node* root = new node(pre[0]);
    //根据当前根节点将中序遍历串分成两子串
    int p = in.find(pre[0]);    //p既是当前根节点在中序子串中的位置，又是中序串中左子树串的长度
    root->lchild = buildTree(pre.substr(1,p), in.substr(0,p)); //建立左子树
    root->rchild = buildTree(pre.substr(p+1,len-p-1), in.substr(p+1, len-p-1)); //建立右子树
    return root;
}

//后序遍历
void postOrder(node* root)
{
    if(root->lchild) postOrder(root->lchild);
    if(root->rchild) postOrder(root->rchild);
    cout<<root->value;
}

int main()
{
    string pre,in;
    while(cin>>pre>>in)
    {
        node* root = buildTree(pre, in);
        postOrder(root);
        cout<<endl;
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <cmath>
#include <map>
#include <vector>

using namespace std;

struct node{
    char value;
    
    node* lchild;
    node* rchild;
};
typedef node* BTNode;

BTNode trans(string s, string t, int l_1,int r_1,int l_2,int r_2)
{
    if(l_1<0 || l_2 < 0 || r_1 >= s.length() || r_2 >= t.length())
    return NULL;
    if(l_1 > r_1 || l_2 > r_2)
    return NULL;
    
    BTNode tnode = (node*)malloc(sizeof(node));
    char c = s[l_1];
    int sp = -1;
    for(int i = l_2;i<=r_2;i++)
    {
        if(t[i] == c)
        {
            sp = i;
            break;
        }
    }
    tnode->value = c;
    tnode->lchild = trans(s,t,l_1+1,r_1,l_2,sp-1);
    tnode->rchild = trans(s,t,l_1+sp-l_2+1,r_1,sp+1,r_2);
    return tnode;
}
vector<char> ans;
void travel(BTNode root)
{
    if(root == NULL)
    return ;
    travel(root->lchild);
    travel(root->rchild);
    ans.push_back(root->value);
}
int main()
{
    string s;
    string t;
    while(cin >> s)
    {
        cin >> t;
        ans.clear();
        BTNode root = trans(s,t,0,s.length()-1,0,t.length()-1);
        travel(root);
        for(int i = 0 ;i<ans.size();i++)
        {
            cout << ans[i];
        }
        cout << endl;
    }
}