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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.02
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @param root TreeNode类 
 * @return bool布尔型
 */
#include <math.h>
#include <stdbool.h>

#define INT_MIN (-pow(2, 31)  )
#define INT_MAX ( pow(2, 31)-1)

bool isValidBSTHelper(struct TreeNode* root, int  lower,  int upper) {
    if (root == NULL) {
        return true;
    }

    if (root->val <= lower || root->val >= upper) {
        return false;
    }

    return isValidBSTHelper(root->left, lower, root->val) && isValidBSTHelper(root->right, root->val, upper);
}

bool isValidBST(struct TreeNode* root) {
    return isValidBSTHelper(root, INT_MIN, INT_MAX);
}

TIPS：

在上述代码中，定义了一个辅助函数 isValidBSTHelper 来递归验证二叉树是否是二叉搜索树。

该函数接受三个参数：root 表示当前节点，lower 表示当前节点的下界，upper 表示当前节点的上界。

初始时，lower 为 INT_MIN，upper 为 INT_MAX，表示根节点没有上界和下界。

在函数中，我们首先判断当前节点的值是否在给定的范围内，如果不在范围内，则返回 false。然后递归验证左子树和右子树，并分别更新上界和下界。最终，如果左子树和右子树都是二叉搜索树且当前节点的值在给定的范围内，那么整棵树就是二叉搜索树，返回 true，否则返回 false。