Recursively solve the traversal of binary trees (often test basic examples)

Suppose that each node of a binary tree is described by a capital letter .

Given the preorder traversal and inorder traversal of this binary tree , Find the postorder traversal .

Input format

Input contains multiple sets of test data .

Each group of data occupies two rows , Each line contains a string of uppercase letters , The first line represents the preorder traversal of the binary tree , The second line represents the middle order traversal of the binary tree .

Output format

Output one row per group of data , A string , Represents the post order traversal of a binary tree .

Data range

The length of the input string does not exceed  26.

Input sample mile ：

ABC
BAC
FDXEAG
XDEFAG

sample output ：

BCA
XEDGAF

Introduction premise ：

The so-called tree Prefix expression , The order is “ Root left and right ”; Infix expression , The order is “ Left root right ”; Postfix expression , The order is “ Left and right ”.

We can know Give the preorder traversal 、 The middle order traversal can calculate the post order traversal .

Give the postorder traversal 、 The middle order traversal can also calculate the pre order traversal .

That is to say , You must traverse with middle order Together, we can push one by two .

  For example ：

The preorder traversal is ：“FDXEAG”, The middle order traversal is ：“XDEFAG”.

  From this we can solve recursively

The code is ：

#include<bits/stdc++.h>
using namespace std;
void dfs(string pre,string in)
{
    if(pre.empty()) return ;
    char root=pre[0];
    int k=in.find(root);
    dfs(pre.substr(1,k),in.substr(0,k));
    dfs(pre.substr(k+1),in.substr(k+1));
    cout<<root;
}
int main()
{
    string pre,in;// Give prefix 、 Infix expression 
    while(cin>>pre>>in)
    {
        dfs(pre,in);// Recursively find the suffix expression 
        cout<<endl;
    }
    return 0;
}