题解 | 判断是不是二叉搜索树

#include <climits>//头文件,这里要使用INT_MIN
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root,INT_MIN, INT_MAX);  
    }
private:
    bool dfs(TreeNode* root,int min,int max){
        if(!root) return true;

        if (root->val<=min||root->val>=max) {
            return false;
        }
        return (dfs(root->left,min,root->val)&&
        dfs(root->right,root->val,max));
    }
};

//方法二:中序遍历验证
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return inorder(root, prev);
    }
    
private:
    bool inorder(TreeNode* node, TreeNode*& prev) {
        if (!node) return true;
        
        // 检查左子树
        if (!inorder(node->left, prev)) {
            return false;
        }
        
        // 检查当前节点（中序遍历应该是递增的）
        if (prev && node->val <= prev->val) {
            return false;
        }
        prev = node;
        
        // 检查右子树
        return inorder(node->right, prev);
    }
};

方法三:迭代中序遍历

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stk;
        TreeNode* curr = root;
        TreeNode* prev = nullptr;
        
        while (curr || !stk.empty()) {
            // 模拟递归：一直向左深入
            while (curr) {
                stk.push(curr);        // 相当于递归调用前的"保存现场"
                curr = curr->left;     // 相当于递归调用 inorder(root->left)
            }
            
            // 模拟递归返回：回到父节点
            curr = stk.top();
            stk.pop();                 // 相当于从调用栈弹出
            
            // 访问当前节点（中序位置）
            if (prev && curr->val <= prev->val) return false;
            prev = curr;
            
            // 转向右子树，模拟递归调用
            curr = curr->right;        // 相当于递归调用 inorder(root->right)
        }
        return true;
    }
};

为什么还需要while(curr)循环？
虽然大部分时间curr的值来自栈，但我们仍然需要while(curr)循环，因为：

1.处理新的子树：每当转向一个非空的右子树时，我们需要从这个新子树的根节点开始，找到它的最左节点

2.统一处理逻辑：这样写代码更简洁，不需要区分"第一次进入"和"后续处理"的情况

3.确保完整性：保证每个新子树的遍历都从中序遍历的起点开始