BST 每日打谱 · 精简版（无重复键）

题目描述

请你实现一个不允许重复键的二叉搜索树（Binary Search Tree, BST）。 按照给定指令依次对 BST 执行操作，并对需要输出的指令打印结果。

• BST 性质：任一节点 x，左子树所有键 < x.key，右子树所有键 > x.key。
• 不允许重复键：插入已存在的键时应忽略（树不改变）。

支持的指令

仅以下 6 类指令；除标明外，其他不输出。

• B n x1 x2 ... xn：Build，依次插入 n 个整数作为初始或增量构建；遇到已存在的键则忽略。（无输出）
• I x：Insert，插入键 x；若已存在则忽略。（无输出）
• F x：Find，若存在键 x 输出 1，否则输出 0。
• P x：Predecessor，输出严格小于 x 的最大键；若不存在输出 NONE。
• S x：Successor，输出严格大于 x 的最小键；若不存在输出 NONE。
• IN：中序遍历（升序）输出当前所有键，键之间以单个空格分隔；若空树输出 EMPTY。

说明：P x 和 S x 的定义与 x 是否在树中无关；它们分别输出 <x 的最大值 与 >x 的最小值。

输入格式

• 第一行：整数 Q（指令条数）。
• 接下来 Q 行：每行一条指令，形式为上述六类之一。

输出格式

• 按输入顺序，仅对 F / P / S / IN 指令各输出一行结果。

数据范围

• 1 ≤ Q ≤ 2 × 10^4
• 键值 x 为整数，|x| ≤ 10^9
• 1 ≤ n ≤ Q（用于 B n ...）
• 初始为空树

样例一

输入

12
B 6 5 3 7 2 4 8
IN
F 3
F 6
P 5
S 5
I 6
IN
I 5
P 2
S 8
IN

输出

2 3 4 5 7 8
1
0
4
7
2 3 4 5 6 7 8
NONE
NONE
2 3 4 5 6 7 8

说明

• 初始构建后集合为 {2,3,4,5,7,8}。
• P 2 无更小键，输出 NONE；S 8 无更大键，输出 NONE。
• 插入已存在的 5 被忽略。

样例二（空树行为）

输入

5
IN
F 10
P 10
S 10
IN

输出

EMPTY
0
NONE
NONE
EMPTY

评测要点与边界

• 插入已存在键需被忽略（树结构不变）。
• P/S 在极值处输出 NONE。
• 空树时 IN -> EMPTY。

• 请严格按定义实现 BST，确保中序遍历为严格升序。

• 这个题目需要自己定义节点的结构体，树采用链式存储。

  struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(){
        val = 0;
    }
  };