题目描述

给定一棵二叉树（不保证为 BST），判断它是否为严格二叉搜索树（BST）：

• 对任意结点 x：其左子树所有键 严格小于 x.val，右子树所有键 严格大于 x.val；
• 不允许重复键（全树范围内键值不得相等）；
• 该定义等价于：中序遍历结果严格升序。

若满足上述条件，输出 YES；否则输出 NO。

输入格式

为便于评测，采用下标表示的树结构（也可用链式存储转化）：

1. 第一行：整数 n（结点个数，\(1 \le n \le 2 \times 10^5\)）。
2. 第二行：n 个整数 val[1..n]，第 i 个为结点 i 的键值（\(|val[i]| \le 10^9\)）。
3. 接下来 n 行：每行两个整数 L R，表示第 i 个结点的左/右孩子下标；若无孩子，用 -1 表示。
4. 约定根为结点 1，保证输入是一棵以 1 为根、无环的有向树（每个结点最多被一个父结点指向）。

输出格式

• 若该树是严格 BST，输出一行 YES；
• 否则输出一行 NO。

判定要点

• 递归校验法：对结点 u 维护允许区间 (low, high)，初始为 (-∞, +∞)；

  • 进入左子树：区间变为 (low, val[u])；
  • 进入右子树：区间变为 (val[u], high)；
  • 要求严格不等（low < val[u] < high），否则 NO。
• 或用一次中序遍历，检查遍历序列是否严格递增（任意相邻两项 a[i] < a[i+1]）。

样例测试

建议用这些用例自测你的程序；每个用例是独立运行的输入/输出。

用例 1：单结点（显然是 BST）

输入

1
5
-1 -1

输出

YES

用例 2：标准 BST（所有左<根<右）

输入

3
2 1 3
2 3
-1 -1
-1 -1

含义：结点1的值为2，左=2(值1)，右=3(值3)。 输出

YES