9048:求后序遍历序列的第k个结点值

Time/Memory Limit:1000 MS/32768 K
Submitted: 740 Accepted: 668

 Problem Description

设有一棵二叉树,其节点值为字符型并假设各值互不相等,采用二叉链表存储表示。现输入其扩展二叉树的前序遍历序列,要求建立该二叉树,并输出其后序遍历序列的第k个结点值(假设该值一定存在)。

 Input

第一行为一个整数n,表示以下有n组数据,每组数据占两行,第一行为一个整数k(1<=k<=二叉树中的结点总数),第二行为扩展二叉树的前序遍历序列。

 Output

输出该二叉树后序遍历序列的第k个结点值。

 Sample Input

2
1
AB#D##C##
4
ABD##E##C#F##

 Sample Output

D
F

 Author

hwt

 Recommend

zh