代码随想录 | Day22 | 二叉树：二叉搜索树中的搜索验证二叉搜索树
代码随想录 | Day22 | 二叉树：二叉搜索树中的搜索&&验证二叉搜索树
主要学习内容：
二叉搜索树的性质：中序遍历是递增序列
700.二叉搜索树中的搜索
700. 二叉搜索树中的搜索 - 力扣（LeetCode）
解法：二分查找
**思路：**如果当前结点t->val大于val就去遍历左子树
如果小于就去遍历右子树
找到了就返回当前结点就是了
1.函数参数和返回值
TreeNode* tra(TreeNode *t,int val)
t为当前节点，val为目标值
2.终止条件
if(t==nullptr || t->val==val)return t;
为空或者找到了都是返回本身
3.本层代码逻辑
其实就是二分查找的三种情况，找到了答案和大于小于搜索值
这三种情况也是互斥的，遍历左子树以后就不会去遍历右子树
if(t==nullptr || t->val==val)return t;
else if(t->val>val)return tra(t->left,val);
elsereturn tra(t->right,val);
完整代码：
class Solution {
public:TreeNode* tra(TreeNode *t,int val){if(t==nullptr || t->val==val)return t;else if(t->val>val)return tra(t->left,val);elsereturn tra(t->right,val);}TreeNode* searchBST(TreeNode* root, int val) {return tra(root,val);}
};
总体来说比较简单
98.验证二叉搜索树
98. 验证二叉搜索树 - 力扣（LeetCode）
解法：中序遍历
**思路1：**首先要知道，二叉搜索树的性质之一是中序遍历会形成一个有序序列
理所当然，通过中序遍历，把树转化为数组，然后分析判断数组中有没有重复元素就行
class Solution {
private:vector<int> vec;void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);vec.push_back(root->val); // 将二叉搜索树转换为有序数组traversal(root->right);}
public:bool isValidBST(TreeNode* root) {vec.clear(); // 不加这句在leetcode上也可以过，但最好加上traversal(root);for (int i = 1; i < vec.size(); i++) {// 注意要小于等于，搜索树里不能有相同元素if (vec[i] <= vec[i - 1]) return false;}return true;}
};
**思路二：**在中序遍历的时候顺手比较一下，看看序列是否是递增的。即设置一个最大值，中序遍历过程中只会遇到更大的值，遇到更大的值说明是正确的，更新他就行，如果遇到了小于等于的说明这并不是二叉搜索树，直接结束验证返回false
1.函数参数和返回值
long long maxVal=LONG_MIN;
bool tra(TreeNode *t)
t为当前节点，maxval为最大值，用来验证序列是否递增，设置为long的最小值是因为测试数据里面有int的最小值
2.终止条件
if(t==nullptr)return true;
if(t->val>maxVal)maxVal=t->val;
elsereturn false;
为空返回true，因为它没有破坏递增的序列
当前结点小于了最大值，那么直接失败
3.本层代码逻辑
中序遍历，典型的左中右，可以判断序列是否递增
bool left=tra(t->left,maxVal);
if(t->val>maxVal)maxVal=t->val;
elsereturn false;
bool right=tra(t->right,maxVal);
return left&&right;
完整代码：
class Solution {
public:long long maxVal=LONG_MIN;bool tra(TreeNode *t){if(t==nullptr)return true;bool left=tra(t->left);if(t->val>maxVal)maxVal=t->val;elsereturn false; bool right=tra(t->right);return left&&right;}bool isValidBST(TreeNode* root) {return tra(root);}
};
错误代码
class Solution {
public:bool tra(TreeNode *t,int maxVal){if(t==nullptr)return true;bool left=tra(t->left,maxVal);if(t->val>maxVal)maxVal=t->val;elsereturn false;bool right=tra(t->right,maxVal);return left&&right;}bool isValidBST(TreeNode* root) {return tra(root,-1);}
};
错误点：
1.使用了参数，这样的话，使用中序遍历当左子树遍历完了以后不会更新最大的val值，if判断的还是会是本层递归函数里的没有更新的maxval，无法判断序列是否递增
测试失败案例：
root=[1,1];
2.没有注意到测试数据最小值，应该传入LONG_MIN.