LC98 · 验证二叉搜索树 · 工程执行实验室
BST 安检门 · 区间通行证
验证 BST 不能只比较父子节点，必须携带祖先传下来的全局上下界。主线讲区间递归法，中序严格递增作为第二视角。
合法 [2,1,4,null,null,3,5] → true
非法 [5,1,6,null,null,4,7] → false
核心 · 区间递归法
验证 BST 不是比较父子，而是携带祖先传下来的全局上下界，递归收紧区间。
- · 每个节点 node.val 必须满足 low < node.val < high。
- · 去左子树时，新的 high = node.val。
- · 去右子树时，新的 low = node.val。
BST 安检门模型
每个节点通过一道「区间闸门」：low 是左闸门，high 是右闸门，node.val 必须严格落在中间。 往左走收紧 high，往右走收紧 low——祖先约束就这样一层层传下去。
不变量
- 1.每个节点 node.val 必须满足 low < node.val < high。
- 2.去左子树时，新的 high = node.val。
- 3.去右子树时，新的 low = node.val。
1/8 · 题目定义
关键步：
Step 1题目定义
不是比较父子，而是验证整棵树
BST 要求左子树所有节点都小于根，右子树所有节点都大于根，并且这个规则在每一层递归成立。合法树 [2,1,4,null,null,3,5] 应返回 true；非法树 [5,1,6,null,null,4,7] 应返回 false。
为什么
验证的是整棵树的排序约束，不是只看相邻父子。
状态表 · 区间通行证
| 当前节点 | low | high | 检查 | 结果 |
|---|---|---|---|---|
| — | — | — | — | — |
动作 · 原因
展示两棵对照树
先建立 BST 全局约束，而不是局部比较。
合法 → true非法 → false
复杂度
- 时间
- O(n)
- 空间
- O(h)，最坏 O(n)
每个节点访问一次，检查区间 O(1)，总共 O(n)。
递归深度等于树高 h；最坏退化成链表时 O(n)。
面试回答
递归 dfs(node, low, high)：空节点返回 true；若 node.val 不在 (low, high) 开区间内返回 false；左子树传 (low, node.val)，右子树传 (node.val, high)。每个节点只访问一次，时间 O(n)，递归栈空间 O(h)，最坏 O(n)。也可用中序遍历检查是否严格递增。
常见误区
误区 1：只比较 node.left 和 node.right
父子局部比较不够。右子树里可能出现小于祖先的值，必须用全局上下界。
误区 2：BST 不允许重复值
必须是严格小于 / 严格大于，不能写成 <= 或 >=。
误区 3：int 边界溢出
用 int 最小值/最大值当边界时要小心溢出；Go 实现可用 *int 或 int64 边界。
误区 4：中序必须严格递增
中序遍历必须严格递增，不是非递减；出现相等或下降都非法。