名册中序查找

入门⏱ 1000ms💾 256MB#P2280🏷️ 搜索树

题目描述

花名册组织成一棵二叉树($n$ 个结点,编号 $1 \sim n$,根为 $1$ 号), 每行给出一个结点的分数与左、右儿子编号($0$ 表示无)。 这棵树是二叉查找树:对它做中序遍历,分数恰好从小到大排列。

现在给定要查找的分数 $x$,按中序顺序查找,输出该分数所在结点在中序遍历中的序号。

输入格式

第一行两个整数 $n$ 和 $x$; 以下 $n$ 行,每行三个整数:结点分数、左儿子编号、右儿子编号(按结点编号 $1 \sim n$ 给出)。

输出格式

一行,一个整数:目标结点在中序遍历中的序号。

数据范围

$$n \le 100$$
,分数为整数且互不相同。

样例输入 #1
7 15
5 2 3
12 4 5
10 0 0
29 0 0
15 6 7
28 0 0
30 0 0
样例输出 #1
4
样例输入 #2
1 5
5 0 0
样例输出 #2
1