LeetCode 98. Validate Binary Search Tree
LeetCode 98. Validate Binary Search Tree
我有一只萌妹子
发布于 2022-06-23 14:01:56
发布于 2022-06-23 14:01:56
https://leetcode.com/problems/validate-binary-search-tree/
这道题是验证一个树是否为二叉搜索树，利用二叉搜索树的性质——二叉搜索树的中序遍历是顺序数组可以轻松的判断。但是，我们这里利用二叉树的定义进行递归的判断。需要注意的是递归判断的过程中，仅仅判断当前左右子结点和根节点的关系是不足以验证的。而要注意右子树的左孩子太小（小于根节点）或者左子树的右孩子太大（大于根节点）的这些情况，因此针对每一个节点，我们用区间来进行判断，代码如下：
class Solution {
public:
bool isValid(TreeNode* root, int* max, int* min){
if( root == nullptr )
return true;
if( min != nullptr && root->val <= *min )
return false;
if( max != nullptr && root->val >= *max )
return false;
return isValid( root->left , &root->val , min ) && isValid( root->right, max , &root->val );
}
bool isValidBST(TreeNode* root) {
return isValid( root, nullptr, nullptr);
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-03-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读