【代码随想录day 19】 力扣 450.删除二叉搜索树中的节点

视频讲解：https://www.bilibili.com/video/BV1tP41177us/?share_source=copy_web&vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E6%80%9D%E8%B7%AF
力扣题目：https://leetcode.cn/problems/delete-node-in-a-bst/

这道题主要是要分清楚删除的节点有几种情况

1. 找不到删除的点
2. 找到了节点，左空右空，即删除的是叶子节点，这种最简单直接删除就好了
3. 左不空右空，直接将父节点跳过连到左子树就行
4. 左空又不空，同上镰刀右子树
5. 左不空又不空，这种是最难的，根据二叉搜索树的特性我们可以将目标节点的左子树全部移到右子树的最左叶子节点。
   这就是这道题的整体思路。
   仍需要注意的是节点的释放，需要保存节点，在删除root节点，否则会出现对空指针的操作。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //终止条件
        //1.没找到删除节点
        if(root == NULL) return NULL;
        //2.找到了
        if(root->val == key)
        {   //删除的是叶子节点
            if(root->left == NULL && root->right == NULL)
            {
                delete root;
                return NULL;
            }
            //3.左不空右空
            else if(root->left != NULL && root->right == NULL )
            {
                auto retNode = root->left;
                delete root;

                return retNode;
            }
            //4.左空右不空
            else if( root->left == NULL&& root->right != NULL)
            {
                auto retNode = root->right;
                delete root;

                return retNode;
            }
            //5.左不空又不空，把节点的左子树放在右子树的左叶子节点后
            else
            {
                TreeNode *cur = root->right;
                while(cur->left!=NULL)
                {
                    cur = cur->left;
                }
                //把左子树放在右子树的左叶子节点后
                cur->left = root->left;

                TreeNode* tmp = root;

                root = root->right;
                delete tmp;
                //不要左子树，直接返回右子树
                return root;
            }
        }
        //单层递归
        if(key < root->val) root->left = deleteNode(root->left, key);
        if(key > root->val) root->right = deleteNode(root->right, key);
        return root;
    }
};