ZeroJudge D432: Secret Code (Pwd)

The “Information Club” has developed a unique passphrase for entering the club. To keep it confidential, the passphrase changes every day. The passphrase consists of a string of distinct uppercase and lowercase English letters and digits from 0 to 9, with a maximum length of 60 characters. Uppercase and lowercase letters are treated as different characters. Each day, the club president places the passphrase into a binary tree that can be generated using the preorder traversal. The inorder and postorder traversal strings of that tree are then sent to all members.
Your task is to write a program that, given the inorder and postorder traversal strings for a particular day, reconstructs the passphrase for that day. The tree traversal methods are described as follows: • In inorder traversal, for any node (root), first output the characters of the left subtree, then the root node’s character, and finally the characters of the right subtree. This pattern is applied to each subtree as well.
•In preorder traversal, for any node (root), first output the root node’s character, then the characters of the left subtree, and finally the characters of the right subtree.
•In postorder traversal, for any node (root), first output the characters of the left subtree, then the characters of the right subtree, and finally the root node’s character.

Sample Inputs/Outputs

Thought Process

Use inorder and postorder to determine the preorder. You can use recursion to slice the strings. Each time you enter the recursion, output the first character of the current inorder string, which is the root. Then, call the functions for the left and right subtrees. You can refer to the problem-solving approach in C126.

Sample Code－ZeroJudge D432: Secret Code (Pwd)

#include <iostream>
using namespace std;

void find(const string middle, const string back) {
    const char root = back[back.length()-1];
    cout << root;
    for (int i = 0; i<middle.length(); i++) {
        if (middle[i] == root) {
            if (i != 0) {
                find(middle.substr(0, i), back.substr(0, i));
            }
            if (i != middle.length()-1) {
                find(middle.substr(i+1, middle.length()-i-1), back.substr(i, back.length()-i-1));
            }
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string middle, back;
    while (cin >> middle >> back) {
        find (middle, back);
        cout << "\n";
    }
}

//ZeroJudge D432
//Dr. SeanXD