题目描述

已知一棵二叉树，中序查找二叉树中值为 $x$ 的结点，并指出它是中序遍历序列中的第几个结点（即结点在中序遍历中的位置序号）。

例如，如图所示的二叉树，其结点值的中序遍历序列为：29、12、8、15、23、5、10。若查找值为 $15$ 的结点，应返回 $4$，表示 $15$ 是中序遍历序列中的第 $4$ 个结点。

输入格式

第一行一个整数 $n$，表示二叉树的结点个数。
第二行一个整数 $x$，表示要查找的结点值。
接下来 $n$ 行，每行三个整数，分别表示一个结点的值、左儿子编号、右儿子编号。
结点的编号按照输入顺序依次为 $1$ 到 $n$，即第 $i$ 行描述的是编号为 $i$ 的结点。若左儿子或右儿子不存在，用 $0$ 表示。

输出格式

输出一个整数，表示值为 $x$ 的结点在中序遍历中的位置序号（从 $1$ 开始计数）。数据保证值为 $x$ 的结点一定存在。

样例

7
15
5 2 3
12 4 5
10 0 0
29 0 0
15 6 7
8 0 0
23 0 0

4

数据范围

• $1 \le n \le 100$
• 各结点的值为整数且互不相同。
• 数据保证树结构合法，且值为 $x$ 的结点一定在树中。

题目来源

CodesOnline