P1827 [USACO3.4] American Heritage

Farmer John takes the ancestry of his cows very seriously, but he is not a great bookkeeper. He represents his cows’ family tree as a binary tree, and records it using the more linear notations of inorder traversal and preorder traversal, rather than drawing the tree. Your task is, given the notations of the cows’ family tree in inorder and preorder traversals, to produce the notation of the postorder traversal. Each cow’s name is encoded as a unique letter. (You may already know that a tree can often be reconstructed if you know two of its traversals.) Obviously, the tree has no more than $26$ vertices. Here is a graphical representation of the tree from the sample input and output: ```plain 　　　　　　　　 C 　　　　　　 / \ 　　　　　　 /　　\ 　　　　　　 B　　 G 　　　　　　/ \　　/ 　　　　 A D H 　　　　　　 / \ 　　　　　　 E F ``` Notes: - Inorder traversal visits nodes in the order: left subtree, root, right subtree. - Preorder traversal visits nodes in the order: root, left subtree, right subtree. - Postorder traversal visits nodes in the order: left subtree, right subtree, root.

The first line contains a string representing the inorder traversal of the tree. The second line contains a string representing the preorder traversal of the tree.

Output a single line representing the postorder traversal of the tree.

Translation from NOCOW. USACO Training Section 3.4. Translated by ChatGPT 5