追溯过去

Grade 100 Open Time Wednesday, 17 June 2020, 5:45 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 5:45 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 5:45 PM
Input file review.in Output file review.out

【题目描述】追溯过去(review)

有魔法师根据量子多宇宙理论,提出了一种搜索方法,该理论是基于这么一个假想:当宇宙面临一种量子选择时,它就分裂成两个不同的宇宙,我们可以将此看做是一棵二叉树,每个结点数据大于左子结点的数据,且要小于右子结点的数据。请根据该二叉树的特征,查找出要找的关键结点。

【输入格式】

第一行为一个整数n,表示有n个整数。

第二行为n个整数,为用数组表示法表示的二叉查找树。

第三行为一个整数k,表示要查找的结点。

【输出格式】

如果查找到结点,输出该数,否则输出“-1”。

【输入样例】

16

0 5 2 9 1 4 7 0 0 0 3 0 6 8 0 0

8

【输出样例】

8