【leetcode】98.验证二叉搜索树

碎碎念

好！好久没刷leetcode了，欠了好多个题解没给自己补上我有罪…以至于现在好多都忘记了当时怎么做的以及有啥问题…我接下来一定及时写啊啊啊啊！
好累好累啊啊啊最近！忙完你的忙你的忙完你的忙你的…看的眼睛酸酸累累的。不管了，既然这篇开坑了就写完它！

一、题目

二、思路和题解

1.思路

难死我了呃呃呃呃呃
做二叉树相关的题目第一反应还是递归了，但由于苯人对二叉搜索树（BST，Binary Search Tree）的概念还是把握的不是很清晰啊于是只考虑一层的：左节点值小于根节点值，右节点值大于根节点值。一旦出现错的就返回false，没有就继续递归左子树和右子树，直到找到最后都没有false就可以返回true了。

但是！！二叉搜索树不是这样的！二叉搜索树要求左子树的所有节点的值都要小于根节点的值，右子树的所有节点的值也要大于根节点的值。所！以！咱们需要用新的min_node和max_node变量来存储当前的上界和下界（所以就要引入辅助函数啦），也就是这个节点在什么样一个范围里才是合法的，如果不在这个范围，那就直接false。

举个合法的二叉搜索树的例子，这里我按照层序来一个个讲：

5 (根节点) / \ 3 7 (3是左子树，7是右子树) / \ / \ 2 4 6 8 (叶子节点)

• 最开始的时候根节点的取值是没有限制的，因此它没有上界和下界；
• 到3这个节点时，按BST的规则，这个节点必须小于父节点的值，所以上界是5，下界依旧没有；
• 到7这个节点时，按BST的规则，这个节点必须大于父节点的值，所以下界是5，上界依旧没有；
• 再往下，到2这个节点时，上界是3，下界没有；
• 到4这个节点就要注意了，它在3的右子树，所以下界是3，但它同时也在5的左子树，所以上界是5；
• 到6节点，一样的，它在7的左子树，所以上界是7，同时它也在5的右子树，所以下界是5；
• 8这个节点在7的右子树，也在5的右子树，所以下界是5和7，取大的，下界是7。

很显然的，每个节点的值都是在合法的范围的，因此这就是一个合法的BST。

这里的上下界我们手工是看的明白的，但在代码里，就需要“继承”一下啦，我们直接看代码！（建议跟着代码走一遍~）

2.代码（递归）

/** * 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) {} * }; */classSolution{public:// 辅助函数，可以“继承”上下界的值，也可以判断是否在范围内boolcheckBST(TreeNode*root,TreeNode*min_node,TreeNode*max_node){// 边界条件if(root==nullptr){returntrue;}// 如果超出下界，不合法if(min_node!=nullptr&&root->val<=min_node->val){returnfalse;}// 如果超出上界，不合法if(max_node!=nullptr&&root->val>=max_node->val){returnfalse;}// 需要接收递归传回来的值，然后查看左右子树是否都合法// 注意这里左节点的下界是继承的，上界更新；右节点的上界是继承的，下界更新returncheckBST(root->left,min_node,root)&&checkBST(root->right,root,max_node);}boolisValidBST(TreeNode*root){// 初始状态上界和下界都是nullreturncheckBST(root,nullptr,nullptr);}};

• 时间复杂度：O(n)
  算法会访问每一个节点恰好一次
• 空间复杂度：O(h)（h是树的高度）
  递归的空间开销来自「函数调用栈」（系统为每个递归调用保存上下文），栈的深度等于递归的最大深度（即树的高度 h）

三、其他解法（中序遍历+判断升序）

1.思路

BST的特点是中序遍历的话是升序的！！

利用这个特点就可以美美解决了，只要不是升序的就是false。

中序遍历请看：【leetcode】94.二叉树的中序遍历（含前序、后序遍历相关内容）

这里我就用的栈模拟了。

2.代码

/** * 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) {} * }; */classSolution{public:// 中序遍历+升序判断boolisValidBST(TreeNode*root){vector<int>res;// 存储遍历结果stack<TreeNode*>st;// 辅助栈TreeNode*cur=root;// 游标指针，从根节点开始// 循环条件：cur非空或栈非空（两者都空说明遍历完成）while(cur!=nullptr||!st.empty()){// 把当前节点的所有左孩子依次入栈if(cur!=nullptr){st.push(cur);cur=cur->left;}else{// 栈顶出栈，访问根节点（加入结果）cur=st.top();st.pop();res.push_back(cur->val);// 处理右子树，游标指向右孩子cur=cur->right;}}//判断是否升序for(inti=0;i<res.size()-1;i++){if(res[i]>=res[i+1]){returnfalse;}}returntrue;}};

• 时间复杂度O(n)
  中序遍历访问每个节点一次，每个节点的入栈 / 出栈操作是 O(1) → 遍历时间 O(n)；
  序列检查遍历 vector 中的 n 个元素，每个元素的比较操作是 O(1) → 检查时间 O(n)；
  总时间 = 遍历 O(n) + 检查 O(n) = O(2n) → O(n)。
• 空间复杂度O(n)
  存储中序序列的 vector res：需要保存 n 个节点值 → 空间 O(n)；
  辅助栈 stack<TreeNode*> st：栈的最大大小等于树的高度 h（和递归栈类似）→ 空间 O(h)；
  总空间 = O(n) + O(h) → 因为 h ≤ n，所以最终空间复杂度 O(n)（主导项是 vector 的 O(n)）

四、错误回顾

1.对BST概念和特点不熟悉，思路上有漏洞，只考虑了一层
2.树的一些基本语法也是手太生了哈，居然都写成root->left.val了…（正确是root->left->val！！！）