代码随想录-二叉搜索树①

目录

二叉搜索树的定义

700. 二叉搜索树中的搜索

题目描述：

输入输出示例：

思路和想法：

98. 验证二叉搜索树

题目描述：

输入输出示例：

 思路和想法：

530. 二叉搜索树的最小绝对差

题目描述：

输入输出示例：

思路和想法：

501.二叉搜索树中的众数

题目描述：

输入输出示例：

思路和想法：

二叉搜索树的定义

二叉搜索树，也称为二叉排序树，是一种特殊的二叉树。它的定义包括以下几点：

1. 若它的左子树不为空，则左子树上所有结点的值都小于根结点的值。
2. 若它的右子树不为空，则右子树上所有结点的值都大于根结点的值。
3. 它的左右子树也分别是二叉搜索树

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

思路和想法：

        利用二叉搜索树的特性进行查找。

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        TreeNode* result = NULL;
        if (root->val > val) result = searchBST(root->left, val);
        if (root->val < val) result = searchBST(root->right, val);
        return result;
    }
};

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

 思路和想法：

class Solution {
public:
    long long maxvalue = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        //二叉树遍历，看是否递增
        if(root == NULL) return true;
        bool left = isValidBST(root->left);     //左
 
        if(root->val > maxvalue){               //中
            maxvalue = root->val;
        }else return false;
 
        bool right = isValidBST(root->right);   //右
 
        return left && right;
 
    }
};

530. 二叉搜索树的最小绝对差

题目描述：

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

输入输出示例：

示例 1：

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

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

• 树中节点的数目范围是 [2, 104]
• 0 <= Node.val <= 105

思路和想法：

class Solution {
public:
    int result = INT_MAX;
    TreeNode* pre = NULL;
    void traversal(TreeNode* cur){
        if(cur == NULL) return;
        traversal(cur->left);       //左
 
        if(pre != NULL){            //中
            result = min(result, cur->val - pre->val);
        }
        pre = cur;
        traversal(cur->right);
 
    }
    int getMinimumDifference(TreeNode* root) {
        if(root == NULL) return 0;
        traversal(root);
        return result;
    }
};

501.二叉搜索树中的众数

题目描述：

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

输入输出示例：

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

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

思路和想法：

class Solution {
public:
    int maxcount = 1;   //最大频率
    int count = 1;      //统计次数
    TreeNode* pre = nullptr;
    vector<int> result;     //存储结果
    void traversal(TreeNode* cur){
        if(cur == nullptr) return;
        traversal(cur->left);
 
        //刚开始遍历时，需要在result里放置元素
        if(pre == nullptr){
            count == 1;
        }
        else if(pre != nullptr){
            if(cur->val == pre->val){
                count ++;
            }else count = 1;
        }
        pre = cur;
 
        if(count > maxcount){
            maxcount = count;
            result.clear();             //数组清空
            result.push_back(cur->val); 
        }
        else if(count == maxcount){
            result.push_back(cur->val);
        }
 
 
        traversal(cur->right);
 
    }
    vector<int> findMode(TreeNode* root) {
        if(root == nullptr) return result;
        traversal(root);
        return result;
    }
};