Day111 | 灵神 | 二叉树 | 验证二叉搜索树

98.验证二叉搜索树

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

方法一：前序遍历

image-20250506121206361

递归函数传入合法的左右边界，只有当前结点是合法的边界，才是二叉搜索树，否则就返回false

对于左子树就传入当前结点的左边界，和当前结点的值作为右边界，从而验证左子树是一颗二叉搜索树

对于右子树就传入当前结点的右边界，和当前结点的值作为左边界，从而验证右子树是一颗二叉搜索树

只有当前结点符合条件并且左右子树也都是二叉搜索树才会返回true

灵神前序遍历代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isValidBST(TreeNode* root, long long left = LLONG_MIN, long long right = LLONG_MAX) {
        if (root == nullptr) {
            return true;
        }
        long long x = root->val;
        return left < x && x < right &&
               isValidBST(root->left, left, x) &&
               isValidBST(root->right, x, right);
    }
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
  • 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。

方法二：中序遍历

二叉树搜索树的中序遍历是一个有序序列，记录前一个值，如果当前结点的值比前一个值小就是false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode *pre=nullptr;
    bool tra(TreeNode *t)
    {
        if(t==nullptr)
            return true;
        bool l=tra(t->left);
        if(pre!=nullptr)
            if(t->val<=pre->val)
                return false;
        pre=t;
        bool r=tra(t->right);
        return l&&r;
    }
    bool isValidBST(TreeNode* root) {
        return tra(root);
    }
};

灵神中序遍历代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    long long pre = LLONG_MIN;
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        if (!isValidBST(root->left) || root->val <= pre) {
            return false;
        }
        pre = root->val;
        return isValidBST(root->right);
    }
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
  • 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。

方法三：后序遍历

灵神后序遍历代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    pair<long long, long long> dfs(TreeNode* node) {
        if (node == nullptr) {
            return {LLONG_MAX, LLONG_MIN};
        }
        auto[l_min, l_max] = dfs(node->left);
        auto[r_min, r_max] = dfs(node->right);
        long long x = node->val;
        // 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
        if (x <= l_max || x >= r_min) {
            return {LLONG_MIN, LLONG_MAX};
        }
        return {min(l_min, x), max(r_max, x)};
    }

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

复杂度分析

  • 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
  • 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。

灵神点评

  • 前序遍历在某些数据下不需要递归到叶子节点就能返回（比如根节点左儿子的值大于根节点的值，左儿子就不会继续往下递归了），而中序遍历和后序遍历至少要递归到一个叶子节点。从这个角度上来说，前序遍历是最快的。
  • 中序遍历很好地利用了二叉搜索树的性质，使用到的变量最少。
  • 后序遍历的思想是最通用的，即自底向上计算子问题的过程。想要学好动态规划的话，请务必掌握自底向上的思想。