Validate Binary Search Tree（验证二叉搜索树）

题目 / Problem

中文： 给定一棵二叉树的根节点 root，判断它是否是一棵有效的二叉搜索树（BST）。

有效二叉搜索树满足：
A valid binary search tree satisfies:

节点的左子树中所有节点值都严格小于该节点值。
Every value in a node's left subtree is strictly less than the node's value.
节点的右子树中所有节点值都严格大于该节点值。
Every value in a node's right subtree is strictly greater than the node's value.
左右子树本身也必须是有效的二叉搜索树。
Both left and right subtrees must also be valid binary search trees.

English: Given the root of a binary tree, determine whether it is a valid binary search tree (BST).

示例 / Examples

Example 1

有效二叉搜索树示例 / Valid binary search tree example

Input:  root = [2,1,3]
Output: true

    2
   / \
  1   3

左子节点 1 < 2，右子节点 3 > 2，所有子树也都满足 BST 条件，因此返回 true。
The left child satisfies 1 < 2, the right child satisfies 3 > 2, and both subtrees are valid, so return true.

Example 2

无效二叉搜索树示例 / Invalid binary search tree example

Input:  root = [5,1,4,null,null,3,6]
Output: false

节点 4 位于根节点 5 的右子树中，却满足 4 < 5，违反了右子树所有值必须严格大于根节点的规则。
Node 4 lies in root 5's right subtree but satisfies 4 < 5, violating the requirement that every right-subtree value be strictly greater than the root.

约束 / Constraints

树中的节点数在 [1, 10⁴] 范围内。
The number of nodes in the tree is in the range [1, 10⁴].
-2³¹ <= Node.val <= 2³¹ - 1

关键点：不能只比较父子节点 / Key Point: Parent-Child Checks Are Insufficient

以下二叉树中，每个节点与它的直接子节点看起来都符合“左小右大”：
In the following tree, every direct parent-child relationship appears to satisfy “left smaller, right greater”:

节点 3 < 6，所以它作为节点 6 的左子节点看似正确。但节点 3 位于根节点 5 的右子树中，必须同时满足 3 > 5，因此整棵树不是 BST。
Node 3 < 6, so it looks valid as the left child of 6. However, it lies in root 5's right subtree and must also satisfy 3 > 5; therefore, the tree is invalid.

每个节点必须满足所有祖先节点传递下来的取值范围，而不只是与父节点比较。
Every node must satisfy the range imposed by all ancestors, not merely its direct parent.

解题思路一：递归上下界 / Approach 1: Recursive Bounds

递归访问每个节点时，携带该节点允许的开区间：
Carry the node's allowed open interval during recursion:

lower < node.val < upper

对于当前节点：
For the current node:

如果 node.val <= lower 或 node.val >= upper，立即返回 false。
If node.val <= lower or node.val >= upper, return false.
访问左子树时，上界缩小为当前节点值：(lower, node.val)。
For the left subtree, reduce the upper bound to the current value: (lower, node.val).
访问右子树时，下界增大为当前节点值：(node.val, upper)。
For the right subtree, raise the lower bound to the current value: (node.val, upper).
只有左右子树都有效，当前子树才有效。
The current subtree is valid only if both subtrees are valid.

根节点开始时没有实际边界，因此使用 -Infinity 和 Infinity。
The root initially has no finite bounds, so use -Infinity and Infinity.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = val ?? 0;
 *   this.left = left ?? null;
 *   this.right = right ?? null;
 * }
 */

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isValidBST(root) {
  function validate(node, lower, upper) {
    if (node === null) {
      return true;
    }

    if (node.val <= lower || node.val >= upper) {
      return false;
    }

    return (
      validate(node.left, lower, node.val) &&
      validate(node.right, node.val, upper)
    );
  }

  return validate(root, -Infinity, Infinity);
}

JavaScript 的 Infinity 和 -Infinity 严格超出所有有限整数，因此即使节点值等于 32 位整数边界，也不会与哨兵值冲突。
JavaScript's Infinity and -Infinity lie strictly beyond all finite integers, so they do not conflict even with 32-bit boundary values.

执行过程 / Walkthrough

以 Example 2 为例：
For Example 2:

当前节点 / Node	允许范围 / Allowed Range	判断 / Result
`5`	`(-∞, +∞)`	有效 / Valid
`1`	`(-∞, 5)`	有效 / Valid
`4`	`(5, +∞)`	`4 <= 5`，无效 / Invalid

节点 4 违反从根节点继承的下界 5，因此无需继续检查其子树，直接返回 false。
Node 4 violates the lower bound 5 inherited from the root, so its subtree need not be examined further; return false.

更深层约束示例 / Deeper Ancestor Constraint

对于：
For:

当前节点 / Node	允许范围 / Allowed Range
`5`	`(-∞, +∞)`
`6`	`(5, +∞)`
`3`	`(5, 6)`

虽然 3 < 6，但 3 不大于下界 5，所以能够正确检测到跨层违规。
Although 3 < 6, it is not greater than lower bound 5, so the deeper violation is correctly detected.

复杂度 / Complexity

设树中有 n 个节点，树高为 h。
Let the tree contain n nodes and have height h.

时间复杂度：O(n)，每个节点最多访问一次。
Time: O(n), because every node is visited at most once.
空间复杂度：O(h)，用于递归调用栈。
Space: O(h) for the recursion stack.
- 平衡树中为 O(log n)。
  It is O(log n) for a balanced tree.
- 树退化为链表时，最坏为 O(n)。
  It is O(n) in the worst case for a skewed tree.

解题思路二：中序遍历 / Approach 2: Inorder Traversal

有效 BST 的中序遍历结果必须严格递增：
The inorder traversal of a valid BST must be strictly increasing:

左子树 → 当前节点 → 右子树
left subtree → current node → right subtree

使用迭代中序遍历，并记录前一个访问值 previous。如果当前值小于或等于前一个值，说明不是有效 BST。
Use iterative inorder traversal and store the previously visited value as previous. If the current value is less than or equal to it, the tree is invalid.

function isValidBSTInorder(root) {
  const stack = [];
  let current = root;
  let previous = -Infinity;

  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();

    if (current.val <= previous) {
      return false;
    }

    previous = current.val;
    current = current.right;
  }

  return true;
}

迭代写法不依赖 JavaScript 递归调用栈。在节点数达到 10⁴ 且树极度倾斜时，它比递归写法更稳妥。
The iterative version does not depend on JavaScript's recursion stack, making it safer for a highly skewed tree with up to 10⁴ nodes.

中序遍历复杂度 / Inorder Complexity

时间复杂度 / Time: O(n)
空间复杂度 / Space: O(h)，显式栈最多保存一条根到叶路径。
The explicit stack holds at most one root-to-leaf path.

两种方法对比 / Approach Comparison

方法 / Method	核心条件 / Core Condition	优点 / Advantage
递归上下界 / Recursive Bounds	每个节点位于祖先限定的开区间内 / Every node lies within inherited bounds	直接对应 BST 定义 / Directly models the definition
迭代中序 / Iterative Inorder	访问值严格递增 / Values are strictly increasing	避免递归栈限制 / Avoids recursion-depth limits

两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(h)。
Both methods take O(n) time and O(h) space.

为什么必须严格比较？ / Why Must Comparisons Be Strict?

题目要求左子树值严格小于节点值，右子树值严格大于节点值，因此重复值会使 BST 无效：
The problem requires left values to be strictly smaller and right values strictly greater, so duplicate values invalidate the BST:

    2
   / \
  1   2   ← 无效 / Invalid

所以边界检查使用 <= 和 >=，中序检查使用 current.val <= previous。
Therefore, bound validation uses <= and >=, while inorder validation checks current.val <= previous.

易错点 / Common Pitfalls

不能只比较节点与它的直接左右子节点，必须考虑所有祖先约束。
Do not compare only direct children; all ancestor constraints matter.
左右子树要求严格小于和严格大于，重复值不合法。
Left and right subtree values must be strictly smaller and greater; duplicates are invalid.
左子树递归更新上界，右子树递归更新下界。
Update the upper bound for the left subtree and the lower bound for the right subtree.
中序遍历结果必须严格递增，不能只是非递减。
Inorder values must be strictly increasing, not merely nondecreasing.
不要使用 32 位最小值和最大值作为初始边界，因为节点值本身可能等于这些边界。
Do not use 32-bit minimum and maximum values as sentinel bounds, because node values may equal them.
极度倾斜的树可能导致递归层数过深，此时可以使用迭代中序遍历。
A highly skewed tree may make recursion too deep; use iterative inorder traversal in that case.

Validate Binary Search Tree