Solution UVA: 536 - Tree Recovery

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss536 - Tree Recovery	Accepted	C++11	0.000	0.000	3551	1 mins ago

Suggest: 
+ To slove problem you need to know Tree Data Structure and Printing a Tree using 3 Methods (but in this problem to save data you can use map not need use node)

*  The most important thing to solve this problem is to realize that: "The root of each subtree will be the character that appears earliest compared to other characters in the first string of the input set"

* Applying the divide and conquer algorithm:

DBACEGF ABCDEFG

Starting with the string ABCDEFG, we can find the root of the largest tree, which is D.

From this position, we divide it into two subtrees: ABC and EFG.

For the ABC subtree, based on the string DBACEGF, we can determine that B is the root (because B appears earliest).

For the EFG subtree, based on the string DBACEGF, we can determine that E is the root (because E appears earliest).

From the ABC subtree, after finding the root as B, we continue to divide and conquer two subtrees: A and C.

From the EFG subtree, after finding the root as E, we continue to divide and conquer one subtree: FG.

For the FG subtree, we find that G is the root (because G appears before F in the first string).

So we have completed finding all nodes in the tree.
Result is Post-order traversal of the tree.

#include<bits/stdc++.h>

using namespace std;

unordered_map<char, char> L, R;

string a, b;

char f(int l, int r){

    if (l==r) return b[l];

           

    int low= 1000111000;

    int root= -1;

   

    for(int i=l; i<=r; i++)

        for(int j=0; a[j]; j++)

            if (b[i] == a[j])

                if (low > j){

                    low = j;

                    root = i;  

                }

   

    if (l <= root-1) L[b[root]]= f(l, root-1);

    if (r >= root+1) R[b[root]]= f(root+1, r);

    return b[root];

}          

void trace(char u){

    if (L.count(u)) trace(L[u]);

    if (R.count(u)) trace(R[u]);

    if ('A' <= u && u <= 'Z') cout<<u;

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    while(cin >> a >> b){

        L.clear(), R.clear();  

        trace(f(0, b.size()));

        cout<<"\n";

    }

}