9060:求最近公共祖先

Time/Memory Limit:1000 MS/32768 K
Submitted: 548 Accepted: 286

 Problem Description

设有一棵非空二叉树,其节点值为字符型并假设各值互不相等,采用顺序存储结构表示。现输入其数组各元素值(空二叉树用'#'表示),建立该二叉树。请设计一个算法,输出编号分别为i和j的两个结点的最近的公共祖先结点的值。

 Input

有多组测试数据,每组数据占两行,第一行为两个整数,分别表示编号i和j(i!=j),第二行为其数组各元素值(空二叉树用'#'表示)。

 Output

输出编号i和j的最近公共祖先结点的值;若给定编号为无效结点,则输出"data error"。

 Sample Input

3 5
ABC#D
2 5
ABCDE#F

 Sample Output

A
B

 Author

hwt

 Recommend

zh