LeetCode 98. Validate Binary Search Tree( 递归，BST )
LeetCode 98. Validate Binary Search Tree( 递归，BST )
ShenduCC
发布于 2020-02-14 12:00:50
发布于 2020-02-14 12:00:50
题意：判断一个二叉树是否为 二叉搜索树BST
题解：所有思路都是去找二叉树中不满足BST性质的节点，找到了，就不符合，找不到就符合。那么怎么去找呢？我提供两种思想。
第一个是，BST的中序遍历是一个有序数组，所以把BST 中序遍历的结果拿出来，看看是不是有序的就可以了。很简单。那如果不让你用额外的空间呢？那就在中序遍历的过程中，判断是不是有序。我们维护一个值last，这个值是遍历数组的前一个元素，如果发现有当前元素小于前一个元素，就是false
第二个思路是，判断每个节点是否符合区间。这种方法随便哪种遍历都可以。根节点的区间，是没有限制的，Int.Min ~ Int.Max。那么左子节点就是Int.Min ~ root->val ，那么左子节点的右子节点，就是root->left->val，root->val。综上所述，每遍历到一个节点时，它的区间的最小值或者最大值都要变成它父亲节点的值，这取决于左子树还是右子树。
这道题目的坑点是，数据范围是 -(1<<31) ~ (1<<31)-1 ,就是int的边界值。
解法一：
int father = -1*(1<<31);
int tag=-1;
bool isValidBST(TreeNode* root) {
if(root==NULL)
return true;
if(isValidBST(root->left))
{
if(root->val>father||(tag==-1&&root->val==father))
{
father = root->val;
tag=1;
return isValidBST(root->right);
}
}
return false;
}第二种
/**
* 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 isValidBST(TreeNode* root) {
if(root==NULL)
return true;
return fun(root,NULL,NULL);
}
bool fun(TreeNode* root,TreeNode* min,TreeNode* max)
{
if(root->left!=NULL)
{
if(!fun(root->left,min,root))
return false;
}
if(root->right!=NULL)
{
if(!fun(root->right,root,max))
return false;
}
if(((min!=NULL&&root->val>min->val)||(min==NULL)) &&(
(max!=NULL&&root->val<max->val )||(max==NULL)))
return true;
else
return false;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-01-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读