难度中等1923收藏分享切换为英文接收动态反馈
给你一个二叉树的根节点 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
1、中序遍历
其实利用二叉搜索树的特性就是：
- 中序遍历是递增或递减序列
- 不存在重复的结点值
利用这两个特性， 我们只要再中序遍历的时候判断即可！
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(root == nullptr)
return true;
// 中序遍历
bool left = isValidBST(root->left);
// 判断是否前一个值大于等于当前的值，是的话说明不符合
if(pre != nullptr && pre->val >= root->val)
return false;
pre = root; // 开始更新pre这个结点为上一个结点
bool right = isValidBST(root->right);
// 最后要返回&&，若有false则都是false
return left && right;
}
private:
TreeNode* pre = nullptr;
};2、迭代
其实就是我们的中序遍历的迭代法，加入了判断二叉搜索树的特性而已！
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
while(cur != nullptr || !st.empty())
{
while(cur != nullptr)
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
st.pop();
// 判断是否有序
if(pre != nullptr && pre->val >= top->val)
return false;
pre = top;
if(top->right)
cur = top->right;
}
return true;
}
private:
TreeNode* pre = nullptr;
};