题目
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
思路和解题方法
第一种方法：
- 首先定义一个辅助函数
traversal，用于实现中序遍历二叉树，并将节点值存储在一个数组vec中。- 然后，调用
traversal函数来遍历二叉树并按顺序存储节点值。- 最后，检查数组
vec是否按照升序排列，若是则为合法的二叉搜索树，返回 true；否则返回 false。第二种方法：
- 定义一个全局变量
maxVal，初始值设为LONG_MIN。- 使用递归函数
isValidBST对二叉树进行深度优先搜索。- 在搜索过程中，先递归遍历左子树，然后判断当前节点的值是否大于
maxVal，若是则更新maxVal为当前节点的值，表示已经访问了当前节点，继续遍历右子树。- 若出现当前节点的值小于等于
maxVal，则说明不满足二叉搜索树的要求，返回 false。- 如果整个搜索过程中没有出现不满足要求的情况，即二叉树是合法的二叉搜索树，返回 true。
第三种方法：
复杂度
时间复杂度:
O(n)
空间复杂度
O(n)
空间复杂度：O(n)，其中 nnn 为二叉树的节点个数。栈最多存储 nnn 个节点，因此需要额外的 O(n)的空间。
c++ 代码一
// 中序遍历二叉树，将节点值按顺序存储在vec数组中
void traversal(TreeNode* root) {
if(root == NULL) return ;
// 遍历左子树
traversal(root->left);
// 将当前节点值加入数组
vec.push_back(root->val);
// 遍历右子树
traversal(root->right);
}
bool isValidBST(TreeNode* root) {
// 清空数组
vec.clear();
// 进行中序遍历
traversal(root);
// 检查数组是否按升序排列
for(int i = 1; i < vec.size(); i++) {
// 若出现逆序，则不是二叉搜索树
if(vec[i] <= vec[i-1]) return false;
}
// 数组按升序排列，是二叉搜索树
return true;
}
c++代码二
long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值
bool isValidBST(TreeNode* root) {
// 到达叶节点，返回true，表示是一个合法的搜索二叉树
if(root == NULL) return true;
// 先递归处理左子树
bool left = isValidBST(root->left);
// 判断当前节点值是否大于maxVal
if(maxVal < root->val)
maxVal = root->val;
else
return false;
// 再递归处理右子树
bool right = isValidBST(root->right);
// 左右子树都是合法的搜索二叉树，整棵树才是合法的
return left && right;
}
c++代码三
TreeNode* pre = NULL; // 用来记录前一个节点
bool isValidBST(TreeNode* root) {
// 到达叶节点，返回true，表示是一个合法的搜索二叉树
if(root == NULL) return true;
// 先递归处理左子树
bool left = isValidBST(root->left);
// 判断当前节点的值是否大于等于前一个节点的值
if(pre != NULL && pre->val >= root->val)
return false;
// 更新pre指针为当前节点
pre = root;
// 再递归处理右子树
bool right = isValidBST(root->right);
// 左右子树都是合法的搜索二叉树，整棵树才是合法的
return left && right;
}
c++迭代法
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st; // 创建一个栈用于存储节点
TreeNode* cur = root; // 初始化当前节点为根节点
TreeNode* pre = NULL; // 初始化前一个节点为NULL，用于记录前一个节点的值
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur); // 将当前节点入栈
cur = cur->left; // 继续遍历左子树, 左
} else {
cur = st.top(); // 弹出栈顶节点作为当前节点， 中
st.pop();
// 判断当前节点值是否小于等于前一个节点的值，如果是，则不是有效的二叉搜索树
if (pre != NULL && cur->val <= pre->val)
return false;
pre = cur; // 更新前一个节点为当前节点
cur = cur->right; // 继续遍历右子树， 右
}
}
return true; // 遍历完整棵树后，没有发现非法节点值，返回true表示是一个有效的二叉搜索树
}
};
觉得有用的话可以点点赞，支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
