验证二叉搜索树
Validate Binary Search Tree
判断一棵二叉树是否为有效的二叉搜索树。
在力扣中练习题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
- 树中节点数目范围在
[1, 104]内 -231 <= Node.val <= 231 - 1
解题思路
上下界 · 递归检查
每个节点都要满足整条祖先链给出的开区间
最直觉的错误写法是“每个节点只和左右孩子比较”。下面这棵树就是反例：9 确实大于父节点 4，但 4 是 8 的左孩子，9 出现在 4 的右子树里就越过了祖先 8 的上界。
根节点没有上下界，允许区间是 (-∞, +∞)；检查会带着区间向下递归。
正确做法是带着区间递归：根的范围是 (-∞, +∞)；进入左子树时上界收紧为当前值，进入右子树时下界收紧为当前值。节点必须严格落在 (low, high) 内。
用节点指针做边界，可以避免 INT_MIN/INT_MAX 被节点值占用的问题；也可以改用 long long。
节点 4 落在 (-∞, 8) 内；左孩子上界收紧为 4，右孩子下界收紧为 4。
自拟树中 9 只和父节点 4 比较是合法的，但 8 给出的上界把它拦住了。每个节点只访问一次，时间 O(n)。
易错点
- 只比较 node 与左右孩子：无法发现“越过祖先”的节点。
- 把区间写成闭区间：BST 通常不允许重复值，等于边界也非法。
- 用 INT_MIN/INT_MAX 当初始边界：节点值恰好等于极值时误判。
中序遍历 · 严格递增
BST 的中序序列必须严格递增
同样 O(n)，但需要 O(h) 显式栈；递归上下界更容易在访问时立刻定位错误。
利用 BST 的定义：中序遍历会得到严格递增的序列。只要在遍历时记录前一个访问的节点，发现 prev->val >= cur->val 就返回 false。
迭代中序用栈实现，不需要额外数组；也可以在递归中维护 prev。
这个方法把“整棵树是否有序”转化为“相邻元素是否有序”，非常简洁，但如果不熟悉中序迭代模板，容易在栈和 cur 的移动上写错。
- 1沿左链压栈，弹出即访问。
- 2比较当前值与上一个访问值。
- 3不满足严格递增返回 false。
- 4遍历结束返回 true。
易错点
- 用 <= 比较而不是 >=：重复值会被误判为合法。
- prev 只在递归返回时更新：比较的就不是中序前驱。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
root = [8,4,12,2,9,10,14]根节点没有上下界，允许区间是 (-∞, +∞)；检查会带着区间向下递归。
查看 C++ 代码
延伸阅读
- BST 的判定必须使用“祖先区间”，不能只看父子关系；同理，删除/插入节点也要维护区间。
- 中序严格递增是等价的判定方式，很多 BST 题都可以先转成中序序列思考。