Description

已知一个二叉树前序遍历、中序遍历的结果，请确定该二叉树并输出其后序遍历的结果。

PS：使用print(data,end=' ')语句输出数据时，便不会换行，而是会接着上次输出的数据继续输出，请同学们自己体验一下这个print的用法。

Input 第一行字符表示待建立二叉树的先序遍历后结果，第二行表示待建立二叉树的中序遍历后结果（元素之间以空格分开）。

例如，输入一个二叉树前序遍历为：A B D E G C F H ，中序遍历为：D B G E A C H F 。那么该二叉树可以确定为：

注意输入最后有一个空格。

Output 输出二叉树后序遍历的结果（元素之间以空格分开）。

Sample Input 1

A B D E G C F H D B G E A C H F Sample Output 1

D G E B H F C A Sample Input 2

A B C D E F G H K B D C A E H G K F Sample Output 2

D C B H K G F E A Sample Input 3

G D A F E M H Z A D E F G H M Z Sample Output 3

A E F D H Z M G Sample Input 4

A B C D E F A B C D E F Sample Output 4

F E D C B A Sample Input 5

a b d h i e j c f g h d i b j e a f c g Sample Output 5

h i d j e b f g c a 分析： 只要清楚了先序中序后序的含义 先序是中左右 中序是左中右 后序是左右中 那么我们只要在递归的： 在先序列里取第一个元素 这个元素就是根元素 然后在中序列里找到根 根的左边（左子树）作为下一次递归的（左）中序列 右边（右子树）作为下一次递归的（右）中序列 然后根据左右边的个数在先序列里截取作为左右的先xulie 先进入右递归 再进入左递归 然后输出根的值

# Determining the Post-order Traverse of Binary Trees Based on Preorder and Mid-order Traverse

def based_on_pre_mid(m: list, n: list):
    if len(n) == 1:
        print(n[0], end=" ")
        return
    elif len(n) == 0:
        return
    else:
        root = m[0]
        k = n.index(root)

        nl = n[:k]
        ml = m[1:len(nl) + 1]
        based_on_pre_mid(ml, nl)

        nr = n[k + 1:]
        mr = m[-len(nr):]
        based_on_pre_mid(mr, nr)

        print(root, end=" ")

a = input().split()
b = input().split()
based_on_pre_mid(a, b)