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

C++算法练习-day42——98.验证二叉搜索树

article 2024/11/23 20:09:47

题目来源：. - 力扣（LeetCode）

题目思路分析

题目：给定一个二叉树，判断它是否是一个有效的二叉搜索树（BST）。

思路：

二叉搜索树（BST）的定义：一个二叉搜索树是一个具有如下性质的二叉树：
- 节点的左子树只包含小于节点值的数。
- 节点的右子树只包含大于节点值的数。
- 左右子树也分别为二叉搜索树。
递归验证：为了验证一个二叉树是否是BST，我们可以使用递归的方法。对于每个节点，我们需要确保：
- 该节点的值大于其左子树中所有节点的值。
- 该节点的值小于其右子树中所有节点的值。
由于我们不能直接访问所有子节点的值（这会导致O(n)的空间复杂度），我们可以使用一个辅助函数，该函数接受当前节点以及该节点值允许的范围（最小值和最大值）作为参数。对于根节点，这个范围是LONG_MIN到LONG_MAX（或int的最小值和最大值，但为了避免整数溢出，使用long long更安全）。
递归终止条件：
- 如果当前节点为空，则返回true（空树是BST）。
- 如果当前节点的值不在允许的范围内，则返回false。
递归调用：
- 对于左子树，更新最大值为当前节点的值，并递归调用验证函数。
- 对于右子树，更新最小值为当前节点的值，并递归调用验证函数。

代码:

#include <climits> // 包含LONG_MAX和LONG_MIN的定义  
  
class Solution {  
public:  
    // 辅助函数，验证以node为根的子树是否是BST，且值在[min, max)范围内  
    bool VaildBST(TreeNode* node, long long min, long long max) {  
        // 如果当前节点为空，返回true（空树是BST）  
        if (!node) {  
            return true;  
        }  
        // 如果当前节点的值不在允许范围内，返回false  
        if (node->val <= min || node->val >= max) {  
            return false;  
        }  
        // 递归验证左子树和右子树  
        // 左子树的最大值更新为当前节点的值  
        // 右子树的最小值更新为当前节点的值  
        return VaildBST(node->left, min, node->val) && VaildBST(node->right, node->val, max);  
    }  
      
    // 主函数，验证以root为根的二叉树是否是BST  
    bool isValidBST(TreeNode* root) {  
        long long max = LONG_MAX; // 初始最大值设为long long的最大值  
        long long min = LONG_MIN; // 初始最小值设为long long的最小值  
        return VaildBST(root, min, max); // 调用辅助函数进行验证  
    }  
};

知识点摘要

二叉搜索树（BST）：一种特殊的二叉树，满足节点的左子树只包含小于节点值的数，右子树只包含大于节点值的数，且左右子树也分别为BST。
递归验证：使用递归方法验证二叉树是否是BST，通过传递当前节点和允许的值范围作为参数。
边界条件：注意处理空节点和节点值超出允许范围的情况。
整数溢出：为了避免整数溢出，使用long long类型来存储最小值和最大值。

通过这道题目，我们学习了如何验证一个二叉树是否是有效的二叉搜索树（BST）。我们使用了递归的方法，并通过传递当前节点和允许的值范围作为参数来确保每个节点的值都满足BST的性质。这种方法不仅简洁而且高效，因为它避免了额外的空间开销来存储所有节点的值。在实际应用中，二叉搜索树是一种非常重要的数据结构，它支持高效的查找、插入和删除操作。通过深入理解BST的性质和验证方法，我们可以更好地利用这种数据结构来解决实际问题。

查看全文

http://www.kler.cn/a/406189.html