POJ 2255/hrbust 2022 Tree Recovery[dfs, 두 갈래 나무의 차원 훑어보기]

Tree Recovery
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 13374
 
Accepted: 8348
Description
Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes. 
This is an example of one of her creations: 

                                               D

                                              / \

                                             /   \

                                            B     E

                                           / \     \

                                          /   \     \

                                         A     C     G

                                                    /

                                                   /

                                                  F

To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG. 
She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it). 
Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree. 
However, doing the reconstruction by hand, soon turned out to be tedious. 
So now she asks you to write a program that does the job for her! 
Input
The input will contain one or more test cases. 
Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.) 
Input is terminated by end of file. 
Output
For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).
Sample Input

DBACEGF ABCDEFG
BCAD CBAD

Sample Output

ACBFGED
CDAB

Source
Ulm Local 1997
제목 대의:
두 갈래 나무의 층이 두루 다니기;너에게 앞의 순서와 중간의 순서를 두루 훑어보게 하고 뒷의 순서를 구하게 하라.
사고방식: 두 갈래 나무의 차원을 두루 훑어본다.
앞의 순서: 뿌리-왼쪽 나무-오른쪽 나무;
중서 역력: 왼쪽 나무-뿌리-오른쪽 나무;
뒷차례 훑어보기: 왼쪽 나무-오른쪽 나무-뿌리;
그 중에서 우리는 앞의 첫 번째 노드가 반드시 뿌리 노드이고 이 뿌리 노드는 중간의 왼쪽은 왼쪽 나무 부분이고 오른쪽은 오른쪽 나무 부분이라는 결론을 얻을 수 있다.
우리가 구축하는 사고방식에 대해 다음과 같다. 중서 반복에서 먼저 전서 반복 안의 첫 번째 노드를 찾으면 왼쪽은 왼쪽 나무이고 오른쪽은 오른쪽 나무이다.그리고 차례차례 해답을 찾으면 우리는 견본을 가지고 실험을 해도 무방하다.
우리는 첫 번째 예시를 예로 들자.
DBACEGF ABCDEFG
디의 위치를 찾아 디:3을 기록합니다.그리고 우리는 우선적으로 오른쪽 나무를 찾는다.
EGF EFG는 E의 위치를 찾아 E:0을 기록하고 오른쪽 트리를 계속 찾습니다.
GF FG는 중서 역행 중 G의 위치를 찾아 G:1을 기록한 다음에 오른쪽 나무를 계속 찾을 수 없다는 것을 발견했다. 우리는 이때 왼쪽 나무를 찾았다. F, FG, F를 기록했다. 이때 우리는 어떤 하위 나무도 역행할 수 없다는 것을 발견했다. 거슬러 올라가면 도중에 진행할 수 있는 왼쪽 나무 dfs가 없다는 것을 발견했다. 이때 위로 거슬러 올라가서 왼쪽 나무 dfs를 진행한다.
DBACEGF ABCDEFG 우리는 왼쪽 트리를 훑어보았는데 과정이 비교적 복잡하다. 여기에 일일이 열거하지 않고 AC 코드에 따라 공부하면 된다.

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
char a[50];char b[50];
int vis[50];
int cont=0;
char ans[50];
void dfs(char a[],char b[])
{
    if(vis[a[0]-'A']==1)return ;
    //printf("%s %s
",a,b);
    ans[cont]=a[0];cont++;
    int p=strchr(b,a[0])-b;
    if(isupper(a[p+1])&&isupper(b[p+1]))dfs(a+p+1,b+p+1);
    if(isupper(a[1]))dfs(a+1,b);
    vis[a[0]-'A']=1;
}
int main()
{
    while(~scanf("%s%s",a,b))
    {
        memset(vis,0,sizeof(vis));
        cont=0;
        dfs(a,b);
        for(int i=cont-1;i>=0;i--)
        {
            printf("%c",ans[i]);
        }
        printf("
");
    }
}