LeetCode 98. 验证二叉搜索树-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 98. 验证二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

LeetCode 98. 验证二叉搜索树,leetcode,算法,职场和发展

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3] 输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。

题解

此题并不难,我们只需要,按照遍历树的思路,在遍历时,测试当前节点与其左右节点的大小关系即可
用递归的方法很容易解决本题

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

typedef struct TreeNode* TreeNode;

bool isValidBST (TreeNode root){
    if(!root) return true;
    
	//在左孩子不为空时,测试当前节点与左孩子的大小关系,如果不符合二叉查找树就返回false
    if(root->left && root->val <= root->left->val ) return false;
    
    //在右孩子不为空时,测试当前节点与右孩子的大小关系,如果不符合二叉查找树就返回false
    if(root->right && root->val >= root->right->val) return false;
    
	//当左右子树都满足二叉查找树时才返回true
    return isValidBST(root->left) && isValidBST(root->right);
}

但当用以上代码测试时,会抛出执行错误

LeetCode 98. 验证二叉搜索树,leetcode,算法,职场和发展

显示这段测试用例不能通过
该用例的图形表示如下
LeetCode 98. 验证二叉搜索树,leetcode,算法,职场和发展
很明显,我们并不能只判断左孩子,右孩子与当前节点的大小关系
在测试一个节点时我们应该规范,其左右孩子的取值范围
所以需要维护一个最大取值,和最小取值
因为题目给定的函数没有维护只两个变量,所以我们另外在写一个函数,再把该函数最终返回的值返回该原函数即可

typedef struct TreeNode* TreeNode;
bool isValid (TreeNode root,int min,int max) {
    if(!root) return true;
    
    if(root->left && root->val <= root->left->val && root->val <= min) return false;
    
    if(root->right && root->val >= root->right->val && root->val >= max) return false;

	//测试左子树,因为左子树的所有节点值都比当前节点小所以将最大值设置为当前节点
	//测试右子树,因为右子树的所有节点值都比当前节点大所以将最小值设置为当前节点
	//当左右子树都满足二叉查找树时才返回true
    return isValid(root->left,min,root->val) && isValid(root->right,root->val,max);
}

bool isValidBST (TreeNode root){
//根据题目描述中节点元素值的取值范围设置初始的最大值和最小值
    return isValid(root,-2147483648,2147483647);
}

现在我们再测试一次
LeetCode 98. 验证二叉搜索树,leetcode,算法,职场和发展
仍然解答错误
因为节点的值可能为边界值,

if(root->left && root->val <= root->left->val && root->val <= min) return false;
if(root->right && root->val >= root->right->val && root->val >= max) return false;

而我们必须把测试范围时的条件设置为 <= 或 >= 以此来避免重复元素出现
所以需要把测试范围扩大
由于扩大测试范围扩大后将超出int所能表示的值所以我们用 long 类型来经行参数传递

typedef struct TreeNode* TreeNode;

bool isValid (TreeNode root,long min,long max) {
    if(!root) return true;

    if(root->left && root->val <= root->left->val || root->val <= min) return false;
    if(root->right && root->val >= root->right->val || root->val >= max) return false;

    return isValid(root->left,min,root->val) && isValid(root->right,root->val,max);
}

bool isValidBST (TreeNode root){
	//扩大测试范围
    return isValid(root,-2147483649,2147483648);
}