代码随想录 | Day22 | 二叉树：二叉搜索树中的搜索&&验证二叉搜索树

主要学习内容：

二叉搜索树的性质：中序遍历是递增序列

700.二叉搜索树中的搜索

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

解法：二分查找

**思路：**如果当前结点t->val大于val就去遍历左子树

如果小于就去遍历右子树

找到了就返回当前结点就是了

1.函数参数和返回值

1
TreeNode* tra(TreeNode *t,int val)

t为当前节点，val为目标值

2.终止条件

1
2
if(t==nullptr || t->val==val)
            return t;

为空或者找到了都是返回本身

3.本层代码逻辑

其实就是二分查找的三种情况，找到了答案和大于小于搜索值

这三种情况也是互斥的，遍历左子树以后就不会去遍历右子树

1
2
3
4
5
6
if(t==nullptr || t->val==val)
	return t;
else if(t->val>val)
	return tra(t->left,val);
else
	return tra(t->right,val);

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
        else
            return tra(t->right,val);
    }
    TreeNode* searchBST(TreeNode* root, int val) {
        return tra(root,val);
    }
};

总体来说比较简单

98.验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

解法：中序遍历

**思路1：**首先要知道，二叉搜索树的性质之一是中序遍历会形成一个有序序列

理所当然，通过中序遍历，把树转化为数组，然后分析判断数组中有没有重复元素就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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.函数参数和返回值

1
2
long long maxVal=LONG_MIN;
bool tra(TreeNode *t)

t为当前节点，maxval为最大值，用来验证序列是否递增，设置为long的最小值是因为测试数据里面有int的最小值

2.终止条件

1
2
3
4
5
6
if(t==nullptr)
	return true;
if(t->val>maxVal)
	maxVal=t->val;
else
	return false;

为空返回true，因为它没有破坏递增的序列

当前结点小于了最大值，那么直接失败

3.本层代码逻辑

中序遍历，典型的左中右，可以判断序列是否递增

1
2
3
4
5
6
7
bool left=tra(t->left,maxVal);
if(t->val>maxVal)
	maxVal=t->val;
else
	return false;
bool right=tra(t->right,maxVal);
return left&&right;

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
        else
            return false; 
        bool right=tra(t->right);
        return left&&right;
    }
    bool isValidBST(TreeNode* root) {
        return tra(root);
    }
};

错误代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
        else
            return 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.