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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    // L: 下界节点 (不为空则当前值必须 > L->val)
    // R: 上界节点 (不为空则当前值必须 < R->val)
    bool Trees(TreeNode* node, TreeNode* L, TreeNode* R){
        if(node==nullptr)
            return true;
        
        // 左子树：必须小于当前节点，且大于下界L
        if(node->left){
            if(L != nullptr && node->left->val <= L->val)
                return false;
            if(node->left->val >= node->val)
                return false;
        }
        // 右子树：必须大于当前节点，且小于上界R
        if(node->right){
            if(node->right->val <= node->val)
                return false;
            if(R != nullptr && node->right->val >= R->val)
                return false;
        }
        // 递归：左子树上界是自己，右子树下界是自己
        return Trees(node->left, L, node) && Trees(node->right, node, R);
    }

    bool isValidBST(TreeNode* root) {
        // 初始状态：没有下界(L=nullptr)，没有上界(R=nullptr)
        return Trees(root, nullptr, nullptr);
    }
};