Tree Delete Node in a BST

https://leetcode.com/problems/delete-node-in-a-bst/#/description
题目大意是实现在一个二叉树中删除一个节点的算法

要删除二叉搜索树中的某个节点p需要考虑三种情况：
1）p有两颗非空子树
2）p是树叶
3）p是只有一颗非空子树

删除p节点的思路
1）要删除的节点p具有两颗非空子树。先将该节点的元素替换为它的左子树的最大元素或右子树的最小元素。
2）要删除的节点是叶子节点 。处理的方法是释放该节点空间，若是根节点，则令根为NULL。
3 ) 要删除的节点p只有一颗子树。如果p没有节点(即p是根节点)，则p的唯一子树的根节点成为新的搜索树的根节点。如果p有父节点pp，则修改pp的指针域，使得它指向p的唯一孩子，然后释放节点p。

以下是我实现的代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        root = deleteNodeitem(root, key);
        return root; 
    }
    
    TreeNode* deleteNodeitem(TreeNode* root, int key){
       
        TreeNode* p = root;//the keynode to delete
        TreeNode* pp = root;//parentNode of the keynode
        TreeNode* s;//the node to replace the keynode
        TreeNode* ps;//parent node of replacenode
         
        //findout the keynode p and its parant node pp
        while((p != NULL)&&(p->val != key)){
            pp = p;
            if(key > p->val){
               p = p->right;    
            }else if(key < p->val){
               p = p->left;
            }
        }
         
        if(p == NULL){
            return root;
         }
       
        //state1 node p have 2 nonull childnode
        if((p->left!=NULL)&&(p->right!=NULL)){
            //find the biggest node in the right tree
            s = p->right;
            ps = p;
            while(s->left != NULL){
                ps = s;
                s = s->left;
            }
           
           TreeNode q = {s->val}; q.left = p->left; q.right = p->right;
            if(pp->left == p){
                pp->left = &q;
            }else if(pp->right == p){
                pp->right = &q;
            }else if(p == root){//要删除的节点就是根节点
                pp->val = q.val;
                cout<< "要删除的节点就是根节点" <<endl;
            }
            
            //make the s node to delete 找出节点s所对应的父节点
            if(ps != p){
                pp = ps;
            }else if((p == ps)&&(p!=root)){//当s的父节点即为p节点时
                pp = &q;
                cout<< "当s的父节点即为p节点时" <<endl;
            }
            p = s;//it must one left child of p if p has child
        }
        
        //statue2 node p have at most one nonull childnode
        TreeNode* pc = p;//the child of p , if it has. 
        if(p->left != NULL){
            pc = p->left;
        }else if(p->right != NULL){
            pc = p->right;
        }else{
            pc = NULL;//p has no child
        }
    
        if(pp->left == p){
            pp->left = pc;
        }else if(pp->right == p){
            pp->right = pc;
        }else{
            root = pc;//根节点就是需要删除的节点
        }
        //  delete p;
        return root;
    }
};

可见代码还是相对繁琐的，下面是其他网友提供的更简洁的算法，大体思路是一样的但利用递归代码量大大的减少

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        if (root->val == key) {
            if (!root->right) {
                TreeNode* left = root->left;
                delete root;
                return left;
            }
            else {
                TreeNode* right = root->right;
                while (right->left)
                    right = right->left;
                swap(root->val, right->val);    
            }
        }
       //利用递归找出左右子树中要删除的节点，并利用该节点的右子树中的左子树的最小节点替换掉要被删除的节点
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};