9066:后序中的首结点

Time/Memory Limit:1000 MS/32768 K
Submitted: 491 Accepted: 326

 Problem Description

设有一棵非空二叉树,其节点值为字符型并假设各值互不相等,采用二叉链表存储表示。设计一个算法,输出该二叉树中以x为根的子树后序遍历序列中的第一个结点值。若不存在以x为根的子树,则输出"not exist"。

 Input

第一行为一个整数n,表示以下有n组数据,每组数据占两行,第一行为结点x的值,第二行为扩展二叉树的前序遍历序列。

 Output

输出该二叉树中以x为根的子树后序遍历序列中的第一个结点值。若不存在以x为根的子树,则输出"not exist"。

 Sample Input

3
A
AB#D##C##
D
ABD##E##C#F##
G
HDA##C#B##GF#E###

 Sample Output

D
D
E

 Author

hwt

 Recommend

zh