题目描述
小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--后序遍历(根在后,从左往右,一棵树的左子树永远在右子树前面,右子树永远在根前面)