一、思路
因为要验证多个节点是否是二叉搜索树,因此使用递归
二、解题方法
设计一个递归函数 helper(root, lower, upper) 来递归判断,函数表示考虑以 root 为根的子树,判断子树中所有节点的值是否都在 (l,r)的范围内(注意是开区间)。如果 root 节点的值 val 不在 (l,r)的范围内说明不满足条件直接返回,否则我们要继续递归调用检查它的左右子树是否满足,如果都满足才说明这是一棵二叉搜索树。
那么根据二叉搜索树的性质,在递归调用左子树时,我们需要把上界 upper 改为 root.val,即调用 helper(root.left, lower, root.val),因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时,我们需要把下界 lower 改为 root.val,即调用 helper(root.right, root.val, upper)。
函数递归调用的入口为 helper(root, -inf, +inf), inf 表示一个无穷大的值。
三、code
class Solution {
public:
bool helper(TreeNode* root,long long lower,long long upper)
{
if(root==nullptr)
{
return true;// 基本情况:子树为空,认为是合法的BST
}
if(root->val <= lower || root->val >= upper)
{
return false;// 节点值不在允许范围内,子树不是有效的BST
}
return helper(root->left,lower,root->val)&&helper(root->right,root->val,upper);
}
bool isValidBST(TreeNode* root) {
return helper(root,LONG_MIN,LONG_MAX);
}
};
=========================================================================学到的知识:
①当程序需要多次检验是否符合条件时,
需要用到递归方法
②结点的值文章来源:https://www.toymoban.com/news/detail-608314.html
root->val文章来源地址https://www.toymoban.com/news/detail-608314.html
到了这里,关于leetcode每日一练-第98题- 验证二叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!