[98、验证二叉搜索树][https://leetcode.cn/problems/validate-binary-search-tree/]

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
前序遍历

通过更新区间，当值不在区间内就返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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) {}
 * };
 */
class Solution {
public:
    bool dfs(TreeNode* root, long start, long end){
        if(root == nullptr){
            return true;
        }
        if(root->val > start && root->val < end){
            return dfs(root->left, start, root->val) && dfs(root->right, root->val, end);
        }else{
            return false;
        }
    }
    bool isValidBST(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        return dfs(root->left, LONG_MIN, root->val) && dfs(root->right, root->val, LONG_MAX);

    }
};
中序遍历

通过维护一个变量pre，逐步比较整个二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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) {}
 * };
 */
class Solution {
public:
    long long pre = LONG_MIN;
    bool dfs(TreeNode* root){
        if(root == nullptr){
            return true;
        }
        bool flag1 = dfs(root->left);
        bool flag2 = false;
        if(root->val > pre){
            flag2 = true;
        }
        pre = root->val;
        bool flag3 = dfs(root->right);
        return flag1 && flag2 && flag3;

    }
    bool isValidBST(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        return dfs(root);


    }
};
后序遍历

先遍历，返回区间，判断节点是不是在范围内

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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) {}
 * };
 */
class Solution {
public:
    long long start = LONG_MAX;
    long long end = LONG_MIN;

    pair<long long, long long> dfs(TreeNode* root){
        if(root == nullptr){
          return make_pair(LONG_MAX, LONG_MIN);  
        }
        pair<long long, long long> left = dfs(root->left);
        pair<long long, long long> right = dfs(root->right);
        long long x = root->val;
        if(x <= left.second || x >= right.first){
            return make_pair(LONG_MIN, LONG_MAX);  
        }
        return make_pair(min(x, left.first), max(x, right.second));
    }

    bool isValidBST(TreeNode* root) {
        return dfs(root).second != LONG_MAX;
    }
};