LeetCode 98. 验证二叉搜索树

题目

难度 中等

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

题解

  这题让我们判断一个数是否是一个二叉搜索树，二叉搜索树的特征就是：节点的左子树只包含**小于**当前节点的数，节点的右子树只包含**大于**当前节点的数，所有左子树和右子树自身必须也是二叉搜索树。这是一个递归的定义，我们这题也可以根据这个定义来进行一个递归的求解。

  当我们知道当前节点的值时，我们就可以知道他所有左子树的数能够取值的范围和他右子树所有能够取值的范围。所以我们这里可以设置两个参数来表示我们的当前值所允许的范围。所以我们需要再创建一个函数bool isBST(TreeNode* root, long long min_num, long long max_num);来进行一个递归的验证。对于每一个结点，我们有三种情况：

1、如果当前的结点为空指针，即表示我们当前的树为二叉搜索树，我们return true

2、如果我们当前的结点的值不在我们的范围之内，则他不是二叉搜索树，return false

3、如果当前的值在我们的范围之内的话，我们就分别验证它的左子树和右子树，左子树的取值范围就为当前的最小值到当前结点的数值[min_num , roor -> val]，右子树的取值范围为当前值到最大值，即[root -> val , max_num]

完整的题解代码为：

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