题目
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。提示：
- 树中节点数目范围在
[1, 104]内 -231 <= Node.val <= 231 - 1
解答
- 基于限定值的递归判断
思路如下：对每一个需要被判断的节点，都为他设置一个最大值和最小值（防止子树的子树不符合搜索树条件），根节点的最大最小值是C++ longlong类型的最大最小值，之后判断左子树时，最大值变更为根节点的值，判断右子树时，最小值变为根节点的值，在判断节点时，若节点为空，则该子树是有效的二叉搜索树，否则就检查当前节点的值是否在minVal到maxVal的范围内。最后递归的验证左子树和右子树。C++实现代码如下：
/**
* 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 isValidBSTHelper(TreeNode* node, long long minVal, long long maxVal) {
// 如果节点为空，则表示该子树是有效的二叉搜索树
if (node == NULL)
return true;
// 检查当前节点的值是否在[minVal, maxVal]的范围内
if (node->val <= minVal || node->val >= maxVal)
return false;
// 递归验证左子树和右子树
return isValidBSTHelper(node->left, minVal, node->val) &&
isValidBSTHelper(node->right, node->val, maxVal);
}
bool isValidBST(TreeNode* root) {
// 由于题目中未指定树节点的值的范围，所以我们使用长整型的最小值和最大值作为初始范围
long long minVal = LLONG_MIN;
long long maxVal = LLONG_MAX;
// 调用辅助函数进行验证
return isValidBSTHelper(root, minVal, maxVal);
}
};