UOJ Logo AYIT Online Judge

AYITOJ

#105. 怪癖小Z

Statistics
时间限制:1s    内存限制:256M    满分: 50分

题目描述

小Z特别喜欢中间的东西,即使那是颗二叉树。一次数据结构课上小Z学到了二叉树,老师在讲台上滔滔不绝的讲,小Z却在下面开小差,他的老毛病又犯了,老是想找到眼前物品的中间的位置的东西,但是由于他没好好听过课,于是就想麻烦精通数据结构的你,帮他找到,这些树每层中间的那个节点并输出这些节点的值

输入描述:

第一行一个整数n,表示节点个数 第二行是这棵二叉树的中序遍历 第三行是这棵二叉树的后序遍历

输出描述:

第一行输出二叉树的层数 接下来每行输出该层的中间节点的值,如果该层节点数是偶数个,则输出中间靠左的那个

样例输入

10
6 5 3 9 4 2 8 10 1 7 
5 6 9 2 4 10 8 3 7 1 

样例输出

5
1
3
6
4
9

数据范围

0<n<=20000

提示:

DLR--前序遍历(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面 ) LDR--中序遍历(根在中,从左往右,一棵树的左子树永远在根前面,根永远在右子树前面) LRD--后序遍历(根在后,从左往右,一棵树的左子树永远在右子树前面,右子树永远在根前面)