C++数据结构与算法——二叉搜索树的修改与构造

一、二叉搜索树中的插入操作（701）

/**
 * 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* insertIntoBST(TreeNode* root, int val) {
        // 判断往哪插
        if(root==NULL){
            TreeNode * inSertVal = new TreeNode(val);
            return inSertVal;
        }
        if(val>root->val){
            // 往右插
            root->right= insertIntoBST(root->right,val);
        }
        else{
            root->left = insertIntoBST(root->left, val);
        }
        return root;
    }
};

二、删除二叉搜索树中的节点（力扣450）

/**
 * 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* deleteNode(TreeNode* root, int key) {
        // 1.没找到值
        if(root==NULL) return NULL;
        if(root->val==key){
            // 2. 左右子树都为空
            if(root->left==NULL&&root->right==NULL) {
                delete root;
                return NULL;
            }
            // 3. 左子树为空 右子树不为空
            else if(root->left==NULL&&root->right!=NULL){
                TreeNode * Rresult = root->right;
                delete root;
                return Rresult;
            }
            // 4. 左子树不为空，右子树为空
            else if(root->left!=NULL&&root->right==NULL){
                TreeNode * Rresult = root->left;
                delete root;
                return Rresult;
            }
            // 5. 左右字数都不为空
            else{
                // 把左子树接到右子树最左侧
                TreeNode * Tright = root->right;
                // 5.1 找到右子树的最左侧
                while(Tright->left!=NULL){
                    Tright = Tright->left;
                }
                // 5.2 把左子树接到右子树最左侧
                Tright->left = root->left;
                // 5.3 返回右子树
                TreeNode * Rresult = root->right;
                delete root;
                return Rresult;
            }
        }
        else if(root->val<key){
            root->right =deleteNode(root->right,key);
        }
        else{
            root->left = deleteNode(root->left,key);
        }
        return root;
    }
};

三、修剪二叉搜索树（力扣669）

/**
 * 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* trimBST(TreeNode * root,int low, int high){
        // 分五种情况
        if(root==NULL) return NULL;
        if(root->val<low){
            // 删除所有左子树
            // 继续向右遍历
            TreeNode* Tright = trimBST(root->right,low,high);
            return Tright;
        }
        else if(root->val>high){
            // 删除右子树
            TreeNode* Tleft = trimBST(root->left,low,high);
            return Tleft;
        }
        
            root->left = trimBST(root->left,low,high);
            root->right = trimBST(root->right,low,high);
        
        return root;
    }
};

四、将有序数组转换为二叉搜索树（力扣108）

/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        TreeNode * root =  traversal(nums,0,nums.size()-1);
        return root;
    }
    TreeNode* traversal(vector<int>& nums,int left,int right){
        if(left>right) return NULL;
        int mid = (left+right)/2;
        TreeNode * root = new TreeNode(nums[mid]);
        root->left = traversal(nums,left,mid-1);
        root->right = traversal(nums,mid+1,right);
        return root;
        
    }
};