98. 验证二叉搜索树
给你一个二叉树的根节点 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
递归
第一反应是,通过遍历判断当前节点和左右子树是否满足左节点<当前节点<右节点。如果仅通过遍历判断当前节点和左右子树是否满足,不能解决右子树中存在小于当前节点的值的问题。违反了节点的右子树只包含大于当前节点的数
的要求。为了解决这个问题,在遍历的时候,参数除了当前节点外,还要给出上界和下界,通过上下界与当前节点的值的比较来判断到当前节点为止,递归路径是否满足题目要求。
对当前节点的判断:
- 当前节点为空,返回
true
,为空说明此条递归路径已经走完了叶子节点,都没有出现问题,则当前路径是满足条件的。 - 不为空,则判断当前节点与上下界是否满足条件;
- 满足,分别进入左右子树,同时上下界更新。
- 不满足,返回
false
注意,题目中的节点值已经到了INT_MAX
和INT_MIN
,所以初始上下界为LONG_MIN,LONG_MAX
查看代码
/**
* 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 work(TreeNode* cur,long long low,long long high){
if(cur==nullptr)//到叶子节点都没有报错,则当前路径是满足有效的
return true;
if(cur->val>low&&cur->val<high)//cur节点是否满足
return work(cur->left,low,cur->val)&&work(cur->right,cur->val,high);//分别进入子树
else
return false;//不满足
}
bool isValidBST(TreeNode* root) {
return work(root,LONG_MIN,LONG_MAX);
}
};
中序遍历
中序遍历按照左 -> 中 -> 右的顺序,中序遍历二叉搜索树,然后判断是否满足元素是升序排列。
查看代码
/**
* 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 isValidBST(TreeNode* root) {
// if(root==nullptr)
// return true;
stack<TreeNode*> sta;
long long lastValue= (long long)INT_MIN - 1;
while(!sta.empty()||root!=nullptr){
while(root!=nullptr){//中序遍历:依次放入左节点,stack先进后出,会依次push出叶子左节点(左)和根节点(中)
sta.push(root);
root=root->left;
}
root=sta.top();//
sta.pop();
if(root->val<=lastValue)//不满足升序,无效
return false;
lastValue=root->val;//更新
root=root->right;//可能为Null,(右)
}
return true;
}
};
MORRIS
使用Morris中序遍历进行判断,介绍可以查看Morris遍历 介绍+前中后序遍历,但是注意但是必须跑完遍历代码,不能像上面一样发现不一致直接return false
,因为Morris
为了实现空间O(1)
修改了二叉树的结构,如果不跑完遍历让其恢复修改,在反序列化时会报错。如这里。因为跑完了遍历,所以用时比前面两个方法久。
查看代码
/**
* 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 isValidBST(TreeNode* root) {
long long lastValue=LONG_MIN;
bool isValid=true;
while (root != NULL)
{
if (root->left == NULL)
{
// cout << root->val << " ";//输出当前节点
if(root->val<=lastValue)//不满足升序,无效
{
isValid=false;
}
lastValue=root->val;//更新
root = root->right;
}
else
{
// 找当前节点的前趋结点
TreeNode* predecessor = root->left;
while (predecessor->right != NULL
&& predecessor->right != root)
{
predecessor = predecessor->right;
}
// 使当前节点成为inorder的前序节点的右侧子节点
if (predecessor->right == NULL)
{
predecessor->right = root;
root = root->left;
}
//复原之前的修改
else
{
predecessor->right = NULL;
// cout << root->val << " ";//输出当前节点
if(root->val<=lastValue)//不满足升序,无效
isValid=false;
lastValue=root->val;//更新
root = root->right;
}
}
}
return isValid;
}
};