二叉树前序中序确定后序 | ||
---|---|---|
Time Limit: 1000 MS | Memory Limit: 1000 KB |
Description
给定二叉树的前序遍历和中序遍历的节点序列,请输出该二叉树的后序遍历节点序列.
Input
输入第一行是一个int型整数n, 表示后面有n组测试数据. 每组数据包含2行, 第1行第1个数字为二叉树中节点数k,后面是前序遍历的k个节点号序列; 第2行第1个数字为二叉树中节点数k,后面是中序遍历的k个节点号序列.
Output
输出n行, 每行为对应二叉树的后序遍历节点序列.
Sample Input
1 9 3 2 8 6 4 5 1 9 7 9 8 2 4 6 3 5 9 1 7
Sample Output
8 4 6 2 9 7 1 5 3