当前位置：首页 > article >正文

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

article 2025/1/27 17:17:43

判断是不是二叉搜索树

- 题目
- 示例
- - 示例 1
  - 示例 2
- 题解
- - 思路
  - 代码实现
  - 代码解释
- 总结

题目

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

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

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

数据范围

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

示例

在这里插入图片描述

示例 1

输入：

{1, 2, 3}

输出：

false

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

示例 2

输入：

{2, 1, 3}

输出：

true

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

题解

思路

二叉搜索树的定义：
- 对于任意一个节点，它的值应该大于左子树所有节点的值，且小于右子树所有节点的值。
- 对于每个子树，都应该满足这个规则。
递归检查：
- 使用递归方法，检查树中每个节点是否满足上述条件。
- 对于每个节点，我们需要维护一个有效值的范围：(min, max)，该范围表示当前节点的值必须大于 min 且小于 max。
- 初始时，根节点的值的范围为 (-∞, ∞)，对于每个节点，递归地更新其左右子树的有效值范围。
算法：
- 对于每个节点，如果其值不在 (min, max) 范围内，则不是二叉搜索树。
- 递归检查左子树时，更新最大值为当前节点的值；递归检查右子树时，更新最小值为当前节点的值。
时间复杂度：
- 每个节点只访问一次，因此时间复杂度为 $O (n)$ ，其中 $n$ 为节点数。
空间复杂度：
- 递归栈的深度最坏情况下为树的高度，因此空间复杂度为 $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);
}

代码解释

TreeNode 结构体：
定义了二叉树节点的结构体，包括节点的值 val、左子树指针 left 和右子树指针 right。
isBST 函数：
- 该函数用于递归检查每个节点是否满足二叉搜索树的条件。
- 如果当前节点为空，则返回 true，表示符合条件。
- 如果当前节点的值不在 (min, max) 范围内，则返回 false。
- 对于当前节点，递归地检查其左子树和右子树，并相应地更新值的范围。
isValidBST 函数：
- 这是主函数，调用 isBST 函数来判断整个树是否为二叉搜索树。
- 初始时，根节点的值的有效范围是 (-∞, ∞)，即使用 LONG_MIN 和 LONG_MAX 来表示。