代码随想录算法训练营第二十二天|235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

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

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

思路：只要利用二叉搜索树特性，只要当前节点的值位于要求的两个节点之间，就必定是我们要找的节点。最简单的一集。

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

二叉搜索树中的插入操作 

题目链接：701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

思路：同样是利用二叉搜索树的性质，自顶向下遍历，大于当前节点就找右子树，小于当前节点就找左子树，直到找到空节点，证明可以插入。

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

        return root;
    }
};

删除二叉搜索树中的节点 

题目链接：450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

思路：和上一题同样的自顶向下遍历二叉搜索树，但是本题难在如何更改树的结构，参考了官方答案，要理清几种不同情况的处理（尤其是要删除的节点的左右子树都存在的情况），同时不要忽略删除的是叶子结点时的情况。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==NULL)return root;
        if(root->val>key)
            root->left=deleteNode(root->left,key);
        else if(root->val<key){
            root->right=deleteNode(root->right,key);
        }
        else{
            if(!root->right){
            TreeNode* node=root;
            root=root->left;
            delete node;
            return root;
            }
            else if(!root->left){
            TreeNode* node=root;
            root=root->right;
            delete node;
            return root;
            }
            else if(!root->right&&!root->left){delete root;return NULL;}
            else{
                TreeNode* cur=root->right;
                while(cur->left){
                    cur=cur->left;
                }
                cur->left=root->left;
                TreeNode* node=root;
                root=root->right;
                delete node;
                return root;
            }
        }

            return root;
    }