二叉搜索树（Binary Search Tree, BST）具有特定的节点值分布规律：对于树中的任意节点，其左子树中所有节点的值必须严格小于该节点的值，其右子树中所有节点的值必须严格大于该节点的值。此外，左右子树自身也必须满足二叉搜索树的定义。

验证一棵二叉树是否为有效的二叉搜索树，通常可以采用以下两种核心思路。

基于中序遍历的验证

二叉搜索树的一个重要性质是，对其进行中序遍历（左-根-右）所得到的节点值序列必定是一个严格递增的序列。因此，我们可以通过中序遍历来检查节点值的递增性。

为了优化空间复杂度，我们不需要将所有节点值存储到数组中再进行比较。可以在遍历的过程中，实时记录并比较当前节点值与前一个访问节点的值。这里采用基于栈的迭代方式实现中序遍历，避免了递归调用栈的额外开销。

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class InOrderValidator {
public:
    bool checkValidBST(TreeNode* root) {
        if (!root) return true;
        
        std::stack<TreeNode*> nodeStack;
        TreeNode* currentNode = root;
        long long previousValue = LLONG_MIN;
        
        while (currentNode != nullptr || !nodeStack.empty()) {
            // 遍历到最左侧的节点
            while (currentNode != nullptr) {
                nodeStack.push(currentNode);
                currentNode = currentNode->left;
            }
            
            // 处理当前节点
            currentNode = nodeStack.top();
            nodeStack.pop();
            
            // 检查是否满足严格递增
            if (currentNode->val <= previousValue) {
                return false;
            }
            previousValue = currentNode->val;
            
            // 转向右子树
            currentNode = currentNode->right;
        }
        
        return true;
    }
};

基于递归与值域边界的验证

另一种高效的验证方式是在深度优先搜索（DFS）的过程中，为每个节点传递其允许的值域上下界。

在遍历每个节点时，我们检查其值是否严格落在给定的下界和上界之间。如果当前节点值合法，则递归检查其左子树和右子树：

• 对于左子树，其上界更新为当前节点的值，下界保持不变。
• 对于右子树，其下界更新为当前节点的值，上界保持不变。

这种方法在发现非法节点时可以立即提前返回，无需遍历整棵树。

class BoundaryValidator {
public:
    bool checkValidBST(TreeNode* root) {
        return validateWithBounds(root, LLONG_MIN, LLONG_MAX);
    }
    
private:
    bool validateWithBounds(TreeNode* node, long long lowerBound, long long upperBound) {
        if (!node) {
            return true;
        }
        
        // 如果当前节点值不在允许的边界范围内，则不是有效的BST
        if (node->val <= lowerBound || node->val >= upperBound) {
            return false;
        }
        
        // 递归验证左右子树，并更新相应的边界值
        return validateWithBounds(node->left, lowerBound, node->val) && 
               validateWithBounds(node->right, node->val, upperBound);
    }
};