代码随想录算法训练营第十七天（二）| 700.二叉搜索树中的搜索 98.验证二叉搜索树

700.二叉搜索树中的搜索

题目：

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

• 树中节点数在 [1, 5000] 范围内
• 1 <= Node.val <= 107
• root 是二叉搜索树
• 1 <= val <= 107

思路：

• 检查当前节点：如果当前节点为空，返回 nullptr，表示没有找到目标值。
• 比较值：如果当前节点的值等于 val，返回当前节点。
• 递归查找：
  • 如果 val 小于当前节点的值，则递归查找左子树。
  • 如果 val 大于当前节点的值，则递归查找右子树。

上代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        // 如果当前节点为空，返回 null
        if (!root) return nullptr;
        
        // 如果当前节点的值等于目标值，返回当前节点
        if (root->val == val) return root;
        
        // 如果目标值小于当前节点的值，递归查找左子树
        if (val < root->val) return searchBST(root->left, val);
        
        // 如果目标值大于当前节点的值，递归查找右子树
        return searchBST(root->right, val);
    }
};

98.验证二叉搜索树

题目：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左

  子树

  只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

思路：

要判断一个二叉树是否是有效的二叉搜索树（BST），我们可以使用递归方法来确保每个节点都符合 BST 的性质。

一个有效的 BST 满足以下条件：

1. 节点的左子树的所有值都小于当前节点的值。
2. 节点的右子树的所有值都大于当前节点的值。
3. 左子树和右子树本身也必须是有效的 BST。

我们可以使用递归方法，结合一个区间来进行检查。

1. 定义一个辅助函数 isValidBST，它会检查当前节点是否在给定的值范围内，并递归检查其左子树和右子树。
2. 范围限制：
   • 对于当前节点，左子树的值必须在 (min, root->val) 范围内。
   • 右子树的值必须在 (root->val, max) 范围内。
3. 递归检查：通过更新范围来递归检查左子树和右子树是否符合 BST 的要求。

上代码;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
   bool isValidBST(TreeNode* root) {
        return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
    }
    
private:
    bool isValidBSTHelper(TreeNode* node, long min, long max) {
        // 如果节点为空，返回 true（空树是 BST）
        if (!node) return true;
        
        // 当前节点的值必须在 min 和 max 范围内
        if (node->val <= min || node->val >= max) return false;
        
        // 递归检查左子树和右子树
        return isValidBSTHelper(node->left, min, node->val) &&
               isValidBSTHelper(node->right, node->val, max);
    }
};