题目描述

给定一棵n个结点的二叉搜索树，要求其中第k小的值（k<=n）。数据保证输入的是二叉搜索树。

输入格式

第一行是一个整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n（1<= n <= 10） ， 根结点为 1。接下来有 n 行， 依次对应二叉树的 n 个结点。 每行有3个整数， 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个（第3个） 数为-1 则表示没有左（右） 儿子。最后一行一个整数表示k（k<=n）。

输出格式

一个整数表示二叉搜索树中第k小的值。

样例

输入样例 1

7
13  2  6
3    3  4
2   -1 -1
5    5  -1
4   -1  -1
15 -1   7
17 -1  -1
4

输出样例 1

5

输入样例 2

5
1 2 3
2 4 5
3 -1 -1
4 -1 -1
5 -1 -1
3

输出样例 2

5

输入样例 3

3
1 2 -1
2 3 -1
3 -1 -1
1

输出样例 3

3

提示

提示：中序遍历二叉搜索树，遍历到第k个结点输出，结束遍历。