题目：二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

思路：因为是搜索二叉树，因此可以使用二叉树的特性来进行搜索

二叉树特性：节点左子树的值都小于该节点，右子树的值都大于该节点。

根据上面的特性可以从上至下搜索树，若第一次碰到节点在目标节点p，q之间说明这个节点就是最近公共祖先。

搜索方式：若此时节点的值都小于目标节点则搜索节点的左子树，若此时的节点的值大于目标节点则搜索节点的右子树

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)    return NULL;
        
        if(root->val > p->val && root->val > q->val)
        {
            TreeNode* left_node = lowestCommonAncestor(root->left,p,q);
            return left_node;
        }
        if(root->val < p->val && root->val < q->val)
        {
            TreeNode* right_node = lowestCommonAncestor(root->right,p,q);
            return right_node;
        }
        if(root->val >= p->val && root->val <= q->val)
        {
            return root;
        }
​
        return root;
        
    }
};

题目：二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

思路：每一个插入的节点都可以在叶子节点处找到对应的位置进行插入，使用二叉搜索树的特性找到对应的叶子节点的位置后插入即可。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr)
        {
            return new TreeNode(val);
        }
​
        if(root->val > val)
        {
            root->left = insertIntoBST(root->left,val);
        }
        else if(root->val < val)
        {
            root->right = insertIntoBST(root->right,val);
        }
        return root;
    }
};

题目：删除二叉搜索树中的节点

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

思路：分清楚删除节点的5钟情况，在代码中详细列出。5种情况种最难的是要删除的左右节点都存在，这种情况的处理方式是将删除节点的左子树接到右子树的最左侧的叶子节点处，因为这个节点是整颗树种值比删除节点大且最接近删除节点的节点。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //情况1：没有找到
        if (root==nullptr) {
            return root;
        }
        if (root->val > key) {
            root->left = deleteNode(root->left,key);
        }
        else if (root->val < key) {
            root->right = deleteNode(root->right,key);
        }
        else {
            // 物种不同的情况
            //情况2，节点在叶子节点处
            if (root->left == nullptr && root->right == nullptr) {
                return nullptr;
            }
            //情况3，节点的左子树有节点
            else if (root->left == nullptr) {
                return root->right;
            }
            //情况4，节点的右子树有节点
            else if (root->right == nullptr) {
                return root->left;
            }
            //情况5，节点的左右子树都有节点
            else {
                TreeNode* tmp = root->right;
                while (tmp->left != nullptr) {
                    tmp = tmp->left;
                }
                tmp->left = root->left;
                return root->right;
            }
        }
        return root;
    }
};