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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <variant>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    struct Inf {};
    using Bound = std::variant<int, Inf>;
    using Range = std::pair<Bound, Bound>;
    bool isValidBST(TreeNode* root) {
        Inf inf;
        auto isInRange = [](const Range& r, auto val) -> bool {
            const auto& [lb, ub] = r;
            bool res = true;
            if(lb.index() == 0) res &= std::get<0>(lb) < val;
            if(ub.index() == 0) res &= val < std::get<0>(ub);
            return res;
        };
        auto check = [&inf, &isInRange](auto&& self, TreeNode* n, Range r) -> bool {
            if (not n) return true;
            const auto& [lb, ub] = r;
            bool res = true;
            res &= self(self, n->left, {lb, n->val});
            res &= self(self, n->right, {n->val, ub});
            return res & isInRange(r, n->val);
        };
        
        return check(check, root, {inf, inf});
    }
};