每日一题-判断是不是二叉搜索树

题目

描述
给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。

二叉搜索树满足以下条件：

• 每个节点的左子树上的所有节点均小于当前节点。
• 每个节点的右子树上的所有节点均大于当前节点。

数据范围

• 节点数量：$1\le n\le 10^4$
• 节点上的值：$-2^{31}\le val\le 2^{31}-1$

示例

示例 1

输入：

{1, 2, 3}

输出：

false

说明：
如题面图1所示，树并不满足二叉搜索树的定义，右子树的值比根节点小。

示例 2

输入：

{2, 1, 3}

输出：

true

说明：
如题面图2所示，树满足二叉搜索树的定义，左子树的值小于根节点，右子树的值大于根节点。

题解

思路

1. 二叉搜索树的定义：

   • 对于任意一个节点，它的值应该大于左子树所有节点的值，且小于右子树所有节点的值。
   • 对于每个子树，都应该满足这个规则。

2. 递归检查：

   • 使用递归方法，检查树中每个节点是否满足上述条件。
   • 对于每个节点，我们需要维护一个有效值的范围：(min, max)，该范围表示当前节点的值必须大于 min 且小于 max。
   • 初始时，根节点的值的范围为 (-∞, ∞)，对于每个节点，递归地更新其左右子树的有效值范围。

3. 算法：

   • 对于每个节点，如果其值不在 (min, max) 范围内，则不是二叉搜索树。
   • 递归检查左子树时，更新最大值为当前节点的值；递归检查右子树时，更新最小值为当前节点的值。

4. 时间复杂度：

   • 每个节点只访问一次，因此时间复杂度为 $O(n)$，其中 $n$ 为节点数。

5. 空间复杂度：

   • 递归栈的深度最坏情况下为树的高度，因此空间复杂度为 $O(h)$，其中 $h$ 为树的高度，最坏情况下 $h=n$（对于链状树）。

代码实现

#include <limits.h>
#include <stdio.h>

/**
 * 结构体定义
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

/**
 * 递归函数，检查当前节点是否满足二叉搜索树的条件
 */
bool isBST(struct TreeNode* root, long min, long max) {
    // 如果当前节点为空，说明符合条件
    if (root == NULL) {
        return true;
    }
    
    // 如果当前节点的值不在(min, max)范围内，则不是二叉搜索树
    if (root->val <= min || root->val >= max) {
        return false;
    }

    // 递归检查左子树，更新最大值为当前节点的值
    // 递归检查右子树，更新最小值为当前节点的值
    return isBST(root->left, min, root->val) &&
           isBST(root->right, root->val, max);
}

/**
 * 主函数，调用递归函数进行二叉搜索树的判断
 */
bool isValidBST(struct TreeNode* root) {
    // 初始时，根节点的有效值范围是(-∞, ∞)
    return isBST(root, LONG_MIN, LONG_MAX);
}

代码解释

1. TreeNode 结构体：
   定义了二叉树节点的结构体，包括节点的值 val、左子树指针 left 和右子树指针 right。

2. isBST 函数：

   • 该函数用于递归检查每个节点是否满足二叉搜索树的条件。
   • 如果当前节点为空，则返回 true，表示符合条件。
   • 如果当前节点的值不在 (min, max) 范围内，则返回 false。
   • 对于当前节点，递归地检查其左子树和右子树，并相应地更新值的范围。

3. isValidBST 函数：

   • 这是主函数，调用 isBST 函数来判断整个树是否为二叉搜索树。
   • 初始时，根节点的值的有效范围是 (-∞, ∞)，即使用 LONG_MIN 和 LONG_MAX 来表示。

总结

通过递归方式检查树中每个节点是否满足二叉搜索树的条件，即每个节点的值要在 (min, max) 范围内，递归地传递这个范围来保证树的正确性。时间复杂度为 $O(n)$，空间复杂度为 $O(h)$。