450. 删除二叉搜索树中的节点

/**
 * 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) {
       if (root == nullptr) 
           return root;
        if (root-> val == key)
        {
            if (root -> left == NULL)    // 如果左子树为空，那么直接返回右子树
            {
                return root -> right;
            }
            auto cur = root -> left;
            auto pre = root;
            while(cur -> right)
            {
                pre = cur;
                cur = cur -> right;
            }
             // cur为等待删除节点，pre为cur的父节点
            if (pre == root)    // 如果pre为root节点，那么直接把root的右子树挂到cur的右子树
            {
                cur -> right = root -> right;
                return cur;
            }
            else
            {
                pre -> right = cur -> left;
                cur -> left = root -> left;
                cur -> right = root -> right;
                return cur;
            }
        }
        else
        {
            root -> left = deleteNode(root -> left, key);
            root -> right = deleteNode(root -> right, key);
            return root;
        }
    }
};