Pre, in and post#1513
A classic problem involving data structures is determining the traversal order of the nodes in a binary tree. There are three standard traversal orders:
Pre-order: visit the root, left subtree, then right subtree;In-order: visit the left subtree, root, then right subtree;Post-order: visit the left subtree, right subtree, then root.
Consider the illustration below:
For the tree above, the pre-order, in-order, and post-order traversals are ABCDEF, CBAEDF, and CBEFDA, respectively. In this problem, given the pre-order and in-order traversals, you are required to find the post-order traversal of the tree.
The first line contains the number of test cases (c \leq 2000). Each of the following lines describes a separate test case and includes the number of nodes (1 \leq n \leq 52) followed by two strings S_1 and S_2, representing the pre-order and in-order traversals of the tree, respectively. The tree's nodes are labeled with distinct characters from a..z and A..Z. The values of , S_1, and S_2 are separated by spaces.
For each test case, output a line containing the sequence of nodes for the post-order traversal of the binary tree.
Example 1