不超过上限的书号

难度：T2

【知识点：二叉搜索树】

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

题目描述

给出一棵合法二叉搜索树及上限 $x$。请输出树中不超过 $x$ 的最大关键字；如果不存在，输出 NONE。不要求树中恰好有 $x$。

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

输入格式

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

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

输出格式

一行一个关键字，或 NONE。

样例输入

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

样例输出

30

样例解释

不超过$30$的最大关键字是$30$。

数据范围

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