C++数据结构与算法——二叉搜索树的属性

C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

文章目录

一、二叉搜索树中的搜索（力扣700）
二、验证二叉搜索树（力扣98）
三、二叉搜索树的最小绝对差（力扣530）
四、二叉搜索树中的众数（力扣501）
五、把二叉搜索树转换为累加树（力扣538）

一、二叉搜索树中的搜索（力扣700）

在这里插入图片描述

/**
 * 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) {
        if(root==NULL||root->val==val) return root;
        TreeNode * result;
        if(root->val<val){
            // 找右子树
            result = searchBST(root->right,val);
        }
        else{
            result = searchBST(root->left,val);
        }
        return result;
    }
};

在这里插入图片描述

二、验证二叉搜索树（力扣98）

在这里插入图片描述

/**
 * 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* pre = NULL;
    bool isValidBST(TreeNode* root) {
        // 使用二叉搜索树的特征，即使用线序遍历，pre结点的值总是比cur结点的值小
        if(root==NULL) return true;
        bool left = isValidBST(root->left);
        if(pre!=NULL){
            if(pre->val>=root->val){
                return false;
            }
        }
        pre = root;
        bool right = isValidBST(root->right);
        return left&&right;
    }
};

在这里插入图片描述

三、二叉搜索树的最小绝对差（力扣530）

在这里插入图片描述

/**
 * 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:
    int minNum = INT_MAX;
    TreeNode * pre=NULL;
    int result;
    void traversal(TreeNode * root){
        // 类似于判断二叉搜索树，使用pre和cur结点
        if(root==NULL) return;
        // 左中右
        traversal(root->left);
        if(pre!=NULL){
            if(root->val-pre->val<minNum){
                minNum = root->val-pre->val;
            }
        }
        pre = root;
        traversal(root->right);
        result = minNum;
    }
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

在这里插入图片描述

四、二叉搜索树中的众数（力扣501）

在这里插入图片描述

/**
 * 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 * pre=NULL;
    int count;
    int maxN =0;
    vector<int> findMode(TreeNode* root) {
        // 同样使用双指针的思想 统计众数
        vector<int> result;
        traversal(root,result);
        return result;
    }
    void traversal(TreeNode* root,vector<int>& result){
        if(root==NULL) return;
        //左
        traversal(root->left,result);
        //中
        if(pre==NULL) count =1;
        else if(root->val!=pre->val) count=1;
        else count+=1;
        // 更新结点
        pre = root;
        if(count>maxN){
            maxN = count;
            result.clear();
            result.push_back(root->val);
        }
        else if(count==maxN){
            result.push_back(root->val);
        }
        // 右
        traversal(root->right,result);      // 右
        return ;
    }
};

在这里插入图片描述

五、把二叉搜索树转换为累加树（力扣538）

在这里插入图片描述

/**
 * 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:
    int pre=0;
    TreeNode* convertBST(TreeNode* root) {
        if(root==NULL) return NULL;
        // 右中左遍历 从小到大
        convertBST(root->right);
        root->val += pre;
        // 更新pre
        pre = root->val;
        convertBST(root->left);
        return root;
    }
};