Can you find Grandparents?
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 37 Accepted Submission(s) : 12
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
想必大家已经知道如何建立二叉排序树了吧.二叉排序树的介绍如链接所示 http://baike.baidu.com/view/922220.htm
例如依次给出9个正整数：8 ,3, 10, 1, 6, 14 ,4 ,7 ,13，建立后的二叉排序树如下图所示.
现在依次给出N个不同的正整数,每个数都不大于10^9,利用这N个有顺序的正整数可以建立出一颗二叉排序树.对于建成的这颗二叉排序树，询问某个节点的祖父节点的值（若该节点没有祖父节点则输出-1）.
例如依次给出9个正整数：8 ,3, 10, 1, 6, 14 ,4 ,7 ,13，建立后的二叉排序树如下图所示.
现在依次给出N个不同的正整数,每个数都不大于10^9,利用这N个有顺序的正整数可以建立出一颗二叉排序树.对于建成的这颗二叉排序树，询问某个节点的祖父节点的值（若该节点没有祖父节点则输出-1）.
Input
含多组样例（小于5组），每组样例为：
第一行一个整数N,M.(0<n<=50000,0<m<=5000)
第二行依次给出N个不同正整数.
第三行到M+2行，每行给出一个正整数T,表示查询值为T节点的祖父节点的值.
第一行一个整数N,M.(0<n<=50000,0<m<=5000)
第二行依次给出N个不同正整数.
第三行到M+2行，每行给出一个正整数T,表示查询值为T节点的祖父节点的值.
Output
对于每组样例输出相应的查询的值。
Sample Input
9 5 8 3 10 1 6 14 4 7 13 8 3 13 14 7 3 3 1 2 3 1 2 3
Sample Output
-1 -1 10 8 3 -1 -1 1
Author
Source
xianbin5