找书经过哪些卡片

难度：T2

【知识点：二叉搜索树】

前置：一维数组、循环、函数、树与遍历

题目描述

图书管理员给出一棵合法二叉搜索树，每个节点保存一个图书关键字。给定目标 $x$，从根开始按相等停止、小向左、大向右的规则查找，报告访问的关键字路径及是否找到。空孩子不计为访问节点。

本题BST的每个节点，其左子树全部关键字更小，右子树全部关键字更大。关键字可为负数或 $0$。

输入格式

第一行两个整数 $n,root$，表示节点数及根的存储编号。接下来 $n$ 行，第 $u$ 行为 val lc rc 三个整数，依次是编号 $u$ 的关键字、左孩子编号、右孩子编号。最后一行是要查找的关键字 $x$。

节点编号为 $1$ 到 $n$，孩子编号 $0$ 表示空；$n=0$ 时 $root=0$ 且没有节点行。非空时保证全部节点从根可达、无环、关键字不同且满足BST规则。

输出格式

第一行输出访问路径，关键字之间用空格隔开；空树输出 EMPTY。第二行找到输出 FOUND，否则输出 MISSING。

样例输入

7 4
30 0 0
10 0 0
60 0 0
40 7 6
90 0 0
70 3 5
20 2 1
30

样例输出

40 20 30
FOUND

样例解释

查找$30$的路径为$40$、$20$、$30$，最后找到。

数据范围

$0\le n\le200$，所有关键字及查询值 $x$在 $-1000$ 到 $1000$ 之间。