LeetCode——98. 验证二叉搜索树

98. 验证二叉搜索树

本次博客，我将记录验证二叉搜索树

由于二叉搜索树的性质是每个节点的左子树中的全部节点数据小于它，而右子树中的全部节点的数据都大于它，因此可以通过这条性质来进行判断

刚上手的时候直接就做了，没考虑到局部最优而非全局最优的情况，遇到这种测试用例直接寄了：

是的，虽然3小于6，7大于6，但是3小于5 /(ㄒoㄒ)/~~

解题思路：

由于上述没有考虑到3小于5的情况，因此在实际写代码的过程中，我们在递归的时候可以加入两个参数upper和lower，即上界和下界

我们首先将upper和lower分别设置为LONG_MAX和LONG_MIN，当处理节点5时，我们向下递归，递归5的左子树时将upper设置为5，递归右子树时将lower设置为5，当处理节点6的左子树时，此时lower是5，upper是6，显然3小于lower，不符合二叉搜索树的条件，返回false即可

代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool dfs(TreeNode* t, long long lower, long long upper){
        if(t==nullptr) return true;
        if(lower>=t->val || upper<=t->val) return false;
        return dfs(t->left, lower, t->val) && dfs(t->right, t->val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return dfs(root, LONG_MIN, LONG_MAX);
    }
};