力扣98、验证二叉搜索树

思路

验证二叉搜索树，就要从它的性质出发；

所以我想到了中序遍历得到一个升序的数列，所以我先找到二叉树最小值，一次从左往右比较；

若发现该数列中存在一个数小于等于其左边的数，直接得到答案，就验证了其不是二叉搜索树，当然一直不存在这个数，我们就得到了它是二叉搜索树

代码如下：自己写的

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
long long mx;
bool flag;
void in_order(struct TreeNode *root) {
    if (root == NULL) return ;
    in_order(root->left);//找到最小值节点
    if (mx >= (long long)(root->val)) { 
        flag = false;
        return ;
    }
    mx = (long long)(root->val);
    in_order(root->right);
    return ;
}

bool isValidBST(struct TreeNode* root) {
    mx = -2147483647 - 1e5;
    flag = true;
    in_order(root);
    return flag;
}

另一种思路写法

bool isBSTUtil(struct TreeNode* root, long long *prev) { 
    if (root) { 
        if (!isBSTUtil(root->left, prev)) 
            return false;
        // 当前结点小于等于它的直接前驱顶点，返回false 
        if (root->val <= *prev) 
            return false; 
        //初始化pre 为当前结点
        *prev = root->val; 
        return isBSTUtil(root->right, prev); 
    } 
    return true; 
}

bool isValidBST(struct TreeNode* root) {
    long long prev = LONG_MIN; 
    return isBSTUtil(root, &prev); 
}

我觉得最好的写法

该想法是先验证左子树或者右子树；

最大值必然在数的最右边，最小值必然在最左边

递归验证每个节点左子树、右子树；

发现不符合条件的子树直接false; 当验证完所有子树时；就返回true;

bool func_min_max(struct TreeNode* root, long min, long max) {
    if (root == NULL) return true;
    if (root->val >= max || root->val <= min) return false;
    return func_min_max(root->left, min, root->val) && func_min_max(root->right, root->val, max); //左右子树都要符合条件
}
bool isValidBST(struct TreeNode* root) {
    return func_min_max(root, LONG_MIN, LONG_MAX);
}