力扣98验证二叉搜索树

二叉搜索树，也叫二叉排序树，满足以下性质：

1. 对于任意节点，（如果有）左子节点小于当前节点，右子节点大于当前节点

算法思路

也是递归吗？递归地去判断左右子节点与当前节点的大小

官方题解中更巧妙的办法是：中序遍历，基于以下性质

• 二叉搜索树的中序遍历一定是升序序列
  
  只需要在中序遍历的过程中，每一步去判断当前值是否大于上一个值就行

递归做法

class Solution {
public:
// 这里为什么用long long呢？主要是节点值取值范围刚好就是int的范围
bool helper(TreeNode* root, long lower, long upper) {
if (root == nullptr) {
return true;
// 当直到再没子节点也没有违反规则
}
if (root->val <= lower || root->val >= upper) {
return false;
// 这里是跟节点值位于开区间内才会通过，如果是int，那么INT_MAX刚好就等于边界条件，无法通过
// 但是long不行吗？不至于long long 吧
}
return helper(root->left, lower, root->val) && helper(root->right, root->val, upper);
// 这里比较的其实是当前节点与他的左右父节点，没有就是祖父左右节点，都没有就是初始正负边界值
}
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
};


但是空间效率很差，递归深了是很费内存的

中序遍历

复习中序遍历

class Solution {
public:
vector inorderTraversal(TreeNode* root) {
vector res;
stack stack;
// 当栈不空或不为空节点，这里或只是保证root!=nullptr能进去
// 这两个while循环写得…如果只满足条件一执行出栈操作肯定没问题
// 如果只满足条件二，那么至少有一步压栈操作（当前根节点），执行出栈也不会有问题
while (!stack.empty() || root != nullptr) {
while (root != nullptr) {
// 递归地把当前节点路径下的所有左子节点入栈
stack.emplace(root);
root = root->left;
// 循环结束，root更新为最深的左子节点的左节点，即为空
}
// 取出栈顶元素
root = stack.top();
stack.pop();

res.emplace_back(root->val);// 插入最深左节点的值
// 最深左节点一定没有左子节点，那么它其实就相当于“中”，接下来是右
// 下一次循环中又以右节点为根节点，去递归压它的左节点
root = root->right;
}
return res;
}
};


题解

只是上面的中序遍历稍作改动

class Solution {
public:
bool isValidBST(TreeNode* root) {
// 用栈来模拟中序遍历
// 之前写的中序遍历用的很简单的递归，迭代感觉比较难
// 这么说的“递归写法相当于隐式维护了一个栈，而迭代就是要把这个栈写出来”
stack stack;
// 排除边界条件
// 为什么这里要减一？上一个解法都没有减一，上一个是LONG_MIN
// long long inorder = INT_MIN - 1;// 这里只保存一步中序遍历的结果
long inorder = LONG_MIN;
while (!stack.empty() || root != nullptr) {
while (root != nullptr) {
// 当节点不为空就压入栈中
stack.push(root);
// 递归地去压左节点？
root = root->left;
}
root = stack.top();
stack.pop();
// 小于前一个中序遍历得到的值，说明不是升序序列，即不是二叉搜索树
if (root->val <= inorder) {
return false;
}
inorder = root->val;// 保存一步中序遍历值
root = root->right;
}
return true;
}
};


时间效率低了很多，空间有比较大的改善，但是仍然不算好