验证二叉搜索树
BST 不是只要求孩子比父节点小或大。每个节点都要通过所有祖先共同留下的开区间安检门。
判断一棵二叉树是否满足严格的二叉搜索树性质。
让祖先约束能跨越多层，正确限制整棵左子树和右子树。
节点必须位于 (low, high)；向左收紧 high，向右抬高 low。
先说结论：这道题到底解决什么
只检查父节点和左右孩子，为什么仍可能把一棵非法二叉搜索树判成合法？递归时应该携带什么信息，才能让每个节点同时服从所有祖先留下的约束？
中心结论：节点必须位于 (low, high)；向左收紧 high，向右抬高 low。
- 1.为什么“左孩子小、右孩子大”只检查了一条边，却没有覆盖整棵子树？
- 2.为什么进入左子树只收紧上界，进入右子树只抬高下界？
- 3.为什么边界必须是严格开区间，并用 int64 表示无穷边界？
完整题目与题意拆解
给定二叉树 root，判断它是否是有效二叉搜索树。有效 BST 的任意节点都满足：左子树所有值严格小于该节点，右子树所有值严格大于该节点。
左右子树本身也必须是 BST，而且标准定义不允许重复值。
- • 约束针对整棵子树，不只是直接孩子。
- • 比较是严格小于与严格大于。
- • 节点值可能位于整数边界。
输入：root = [5,1,4,null,null,3,6]
输出：false
原因：3 位于根 5 的右子树，却小于 5。“左小右大”是一句容易被误解的缩写。准确说法是：左子树中的每一个值都小于当前节点，右子树中的每一个值都大于当前节点。
因此后代节点除了满足父节点，还必须继续满足祖父、曾祖父留下的范围。
局部相邻比较为什么会被骗
镜头先只展示父子边，再拉远显示根节点留下的跨层限制，让学习者亲眼看到“边没错、整棵树仍然错”。
第一层方案：暴力做法
可以对每个节点扫描其整棵左子树的最大值和右子树的最小值，再递归验证子树。
这种方法会反复遍历后代，链状树最坏达到 O(n²)。它揭示了真正需要的信息：每个节点都受一个全局范围约束。
对每个 node：
max(node.Left) < node.Val
min(node.Right) > node.Val
再验证左右子树错误模型在哪里丢掉了信息
沿左、右子树逐步移动区间门，突出如果每层重新开始比较，就会忘记更早祖先已经设定的另一侧边界。
优化方向：需要一种能随递归向下传播的状态。允许区间 (low, high) 正好把所有祖先约束压缩成两个边界。
整体地图：先做什么，再做什么
先用 [5,1,4,null,null,3,6] 击穿局部比较：4 小于它的父节点 5? 这个例子里真正的问题是右子树中的 4 和 3 都没有满足根节点 5 留下的下界。局部边看起来可以逐条成立，但祖先约束已经在更高层被丢失。
然后把递归函数定义为 valid(node, low, high)：它不只是“检查 node”，而是在证明以 node 为根的整棵子树都落在开区间 (low, high) 中。每向下一层，只更新由当前节点新产生的那一侧边界。
- • 反例负责说明旧模型缺了什么信息。
- • 开区间负责把所有祖先约束压缩成两个边界。
- • 递归返回值负责把子树结论交还给父节点。
把祖先规则压缩成每个节点随身携带的通行区间
根节点一开始可以位于 (-∞,+∞)。如果当前值是 value，那么左子树的所有节点都必须小于 value，因此左侧递归得到 (low,value)；右子树的所有节点都必须大于 value，因此右侧递归得到 (value,high)。
low 和 high 不是只来自父节点，而是整条祖先路径上所有限制的交集。一个深层节点只要越过其中任意一条祖先边界，就应立即失败。
在根 5 的右子树里，即使节点 4 小于自己的父节点，它仍必须满足 low=5；4 <= 5，所以直接判错。开区间就是节点的通行证
每到一个节点，画面先展示它当前允许的开区间，再判断节点值能否穿过两扇严格边界门。
先验当前节点，再把更窄的区间交给左右子树
递归首先处理 nil：空子树没有违规节点，因此返回 true。随后把 node.Val 转成 int64，并检查 value <= low 或 value >= high；等号也失败，因为题目中的 BST 不允许重复值。
当前节点通过后，左侧调用 valid(node.Left,low,value)，右侧调用 valid(node.Right,value,high)，最后只有两边都为 true 才返回 true。检查顺序让越界节点可以尽早短路。
- • nil 返回 true，是“空集合满足约束”，不是找到了一个节点。
- • 左递归保留旧 low，只用当前值替换 high。
- • 右递归保留旧 high，只用当前值替换 low。
- • int64 的最小值和最大值避免与合法 int 节点值冲突。
递归函数 valid(node, low, high) 负责判断当前子树是否全部落在允许范围内。nil 子树天然有效。
当前值越界立即 false；否则递归验证左右子树，只有两边都有效才返回 true。
左边收高，右边抬低
动画把当前值复制成新边界：进入左子树替换 high，进入右子树替换 low，同时保留另一侧祖先边界。
为什么两个边界足以代表所有祖先约束
递归不变量是：进入 valid(node,low,high) 时，(low,high) 正好等于从根到 node 的全部祖先约束的交集。根节点没有祖先，因此使用无穷区间。
若当前 value 不在区间中，它违反至少一条祖先规则，返回 false 必然正确。若它在区间中，左子树新增 value 上界，右子树新增 value 下界；其余祖先限制原样保留，所以两个递归调用继续满足同一不变量。
当递归到 nil 时没有节点可违反规则。由子树结构归纳可知，左右子树都通过且当前节点通过，当且仅当整棵当前子树满足 BST 定义。
- • 递归参数 (low,high) 等价于所有祖先约束的交集。
- • 当前值通过区间后，左子树只新增 value 上界，右子树只新增 value 下界。
- • 两棵子树都有效时，当前子树的所有节点才满足 BST 定义。
完整执行过程
动画把区间画成安检门。重点看边界沿树边传播：向左改变 high，向右改变 low，祖先另一侧的限制始终保留。
- 1从根 5 开始，允许区间是 (-∞,+∞)，5 通过检查。
- 2进入左节点 1，区间收紧为 (-∞,5)，1 通过；它的空孩子返回 true。
- 3进入右节点 4，区间不是局部的 (-∞,+∞)，而是祖先留下的 (5,+∞)。
- 44 <= 5，违反严格下界，当前递归立即返回 false。
- 5false 沿调用栈向上传播，整棵树被正确判定为非法 BST。
在深层越界处立即失败
完整跑过反例，在节点 4 处显示 low=5，并让失败结果沿递归调用链返回到根节点。
把动画和 Go 代码逐行对应
每一帧使用稳定的语义行 ID，不依赖容易漂移的数字行号。先观察分支为什么成立， 再看对应代码，而不是先背模板。
区间状态如何落到 Go 代码
同步高亮 nil 基线、严格范围判断和左右递归参数，逐行对应画面中的区间变化。
3 位于根 5 的右子树，还必须满足 3 > 5，这一点局部检查看不到。
根节点没有祖先，不受有限上下界限制。
根 5 的整个左子树都必须严格小于 5。
空集合不包含违反区间的节点，是递归正确终止的基础。
根 5 的整个右子树都必须严格大于 5，不只是直接右孩子。
右子树中的任何值都必须大于根 5；无需再检查 4 的孩子。
当前节点只增加一条新约束，但祖先留下的另一条约束仍然有效。
标准 BST 的左右关系是严格不等，不允许重复值。
每个被访问节点只做一次区间比较，栈深由树高决定。
完整 Go 提交代码与最小测试
1func isValidBST(root *TreeNode) bool {2 return valid(root, math.MinInt64, math.MaxInt64)3}4 5func valid(node *TreeNode, low, high int64) bool {6 if node == nil { return true }7 value := int64(node.Val)8 if value <= low || value >= high {9 return false10 }11 12 leftOK := valid(node.Left, low, value)13 rightOK := valid(node.Right, value, high)14 return leftOK && rightOK15}// 合法 BST
fmt.Println(isValidBST(buildTree([]any{2, 1, 3}))) // true
// 深层节点违反祖先边界
fmt.Println(isValidBST(buildTree([]any{5, 1, 4, nil, nil, 3, 6}))) // false
// 重复值不满足严格开区间
fmt.Println(isValidBST(buildTree([]any{2, 2, 2}))) // false
// 单节点与 int 极值也应合法
fmt.Println(isValidBST(&TreeNode{Val: math.MinInt})) // true正确性与复杂度
有效树需要检查每个节点一次；无效树可能更早在越界处短路。
递归栈深度由树高 h 决定，平衡树 O(log n)，退化树最坏 O(n)。
最容易写错的地方
只检查直接左右孩子。
递归到孙子时丢失祖先留下的另一侧边界。
使用 <= 或 >= 的错误方向，接受重复值。
用节点可能取到的 int 值充当无穷边界。
最后复盘：带走逻辑链
- 1.BST 规则约束整棵子树，不是只约束一条边。
- 2.每个节点携带开区间 (low,high)。
- 3.左边收紧 high，右边抬高 low。
- 4.替代思路是中序严格递增，但不要在同一次讲解中混用两套状态。
- 1.只比较父子节点不够，因为祖先约束会跨越多层。
- 2.定义 valid(node,low,high)，要求 node.Val 严格位于开区间内。
- 3.向左递归把 high 改成当前值，向右递归把 low 改成当前值。
- 4.用 int64 边界避免极值冲突；时间 O(n)，递归空间 O(h)。