验证二叉搜索树 | 秋招知识库

视频讲解

请看【基础算法精讲 11】，制作不易，欢迎点赞关注~

方法一：前序遍历

$dfs$ 额外传入两个参数，分别表示从根到当前节点路径上的最小值和最大值。

当前节点的值必须在最小值和最大值之间（不能等于）。原理见视频。

答疑

问：为什么 Java 等语言要用 $long$ 类型？题目不是只有 $int$ 类型吗？

答：虽然题目是 $int$ 类型，但开始递归的时候， $left$ 需要比所有节点值都要小， $right$ 需要比所有节点值都要大，如果节点值刚好是 $int$ 的最小值/最大值，就没有这样的 $left$ 和 $right$ 了，所以需要用 $long$ 类型。

Python 解法1C++ 解法1

python

class Solution:
    def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:
        if root is None:
            return True
        x = root.val
        return left < x < right and \
               self.isValidBST(root.left, left, x) and \
               self.isValidBST(root.right, x, right)

cpp

// C++ 版待补充

C++ 解法2

cpp

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)$ 的栈空间。

方法二：中序遍历

本题是二叉搜索树，中序遍历是自然的做法。

中序遍历时，可以把二叉搜索树看成一个有序数组。

怎么判断一个数组是有序数组？比较相邻元素的大小即可。

答疑

问：如何证明，如果二叉树的中序遍历是严格递增的，那么二叉树一定是二叉搜索树？

答：已知条件为，中序遍历是严格递增的。我们要证明这棵二叉树是二叉搜索树。对于这棵二叉树的任意节点 $x$ ，中序遍历中的在 $x$ 左边的点都是遍历过的点，这包含 $x$ 的左子树，所以 $x$ 的左子树的节点值都严格小于 $x$ 的节点值。中序遍历中的在 $x$ 右边的点都是未遍历过的点，这包含 $x$ 的右子树，所以 $x$ 的右子树的节点值都严格大于 $x$ 的节点值。所以这棵二叉树的每个节点都满足二叉搜索树的性质，所以这棵二叉树是二叉搜索树。

Python 解法3C++ 解法3

python

class Solution:
    pre = -inf

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        if not self.isValidBST(root.left):  # 左
            return False
        if root.val <= self.pre:  # 中
            return False
        self.pre = root.val
        return self.isValidBST(root.right)  # 右

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
    long long pre = LLONG_MIN;
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        if (!isValidBST(root->left)) { // 左
            return false;
        }
        if (root->val <= pre) { // 中
            return false;
        }
        pre = root->val;
        return isValidBST(root->right); // 右
    }
};

复杂度分析

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

方法三：后序遍历

$dfs$ 返回子树的最小值和最大值，供上面的节点判断是否为二叉搜索树。

Python 解法5C++ 解法5

python

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode]) -> Tuple:
            if node is None:
                return inf, -inf
            l_min, l_max = dfs(node.left)
            r_min, r_max = dfs(node.right)
            x = node.val
            # 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
            if x <= l_max or x >= r_min:
                return -inf, inf
            return min(l_min, x), max(r_max, x)

        return dfs(root)[1] != inf

cpp

// C++ 版待补充

C++ 解法6

cpp

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)$ 的栈空间。

点评

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

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

方法一：前序遍历 ​

答疑 ​

复杂度分析 ​

方法二：中序遍历 ​

答疑 ​

复杂度分析 ​

方法三：后序遍历 ​

复杂度分析 ​

点评 ​

分类题单 ​

视频讲解

方法一：前序遍历

答疑

复杂度分析

方法二：中序遍历

答疑

复杂度分析

方法三：后序遍历

复杂度分析

点评

分类题单