ZeroJudge C126: Tree Recovery

UVa 00536 – Tree Recovery

Little Valentine loves binary trees very much. She often constructs binary trees randomly using uppercase English letters. Here is one of them:

D
/ \
/ \
B E
/ \ \
/ \ \
A C G
/
/
F

To preserve the binary tree, for each binary tree, she writes down two types of strings: the preorder traversal (root, left subtree, right subtree) and the inorder traversal (left subtree, root, right subtree). For the binary tree mentioned above, she wrote the preorder traversal string: DBACEGF and the inorder traversal string: ABCDEFG.

Your task is to reconstruct the original binary tree from the strings Little Valentine wrote down and then print the tree in postorder traversal (left subtree, right subtree, root).

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The input is provided until EOF, with each line representing one test case. Each line contains two strings, representing the preorder and inorder traversal results of a binary tree. Both strings consist only of uppercase English letters, and there are no duplicate letters. Therefore, the maximum length of each string is 26.For each input line, output the postorder traversal result of the corresponding binary tree.
DBACEGF ABCDEFG
BCAD CBAD		ACBFGED
CDAB

Thought Process

The order of preorder traversal is: root, left, right.

The order of inorder traversal is: left, root, right.

Using a recursive approach, set the root as the first character of the preorder string in each call. Then, use a for loop to search for the root in the inorder string. Once the root is found, recursively call the function for the left and right parts of the tree, divided based on the position of the root in the inorder string.

Left Subtree: Take the substring of the preorder string starting from position 1 and extending i characters to the right, where i is the index of the root in the inorder string. Similarly, take the substring of the inorder string from position 0 to i. If the root is at position 0 in the inorder string, there’s no need to call the function for the left subtree.

Right Subtree: Take the substring of the preorder string starting from position i+1 and extending preorder.length() - i - 1 characters to the right. Similarly, take the substring of the inorder string from position i+1 to the right, extending preorder.length() - i - 1 characters. If the root is not at the last position in the inorder string, then there’s no need to call the function for the right subtree.

After each function call for the left and right subtrees, you need to output the root of the current subtree. This ensures that the root is printed after processing both the left and right subtrees, which corresponds to the postorder traversal order (left, right, root).

Sample Code－ZeroJudge C126: Tree Recovery

#include <iostream>
using namespace std;

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

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

//ZeroJudge C126
//Dr. SeanXD
Tags

Related Posts

Comments