在二叉搜索树中删除结点要比插入结点复杂得多，在当前递归层级一共要考虑五种不同的情况：
● 当前递归结点 (root) 为空，表明没有找到要删除的结点，返回 NULL；
● 当前递归结点 (root) 为叶子结点，直接删除并将空结点返回上层；
● 当前递归结点 (root) 左子树为空但右子树不空，用 root 的右子树替代 root 的位置；
● 当前递归结点 (root) 右子树为空但左子树不空，用 root 的左子树替代 root 的位置；
● 当前递归结点 (root) 左右子树都不空，把 root 的左子树，挂在 root 右子树的最左侧结点 (即 root 的中序后继) 的左子树处，再用 root 的右子树替代 root 的位置。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root == NULL) // 没有找到待删除结点，直接返回
return NULL;
if(root->val == key) { // 当前结点即为待删除结点
if(root->left == NULL && root->right == NULL) { // 当前结点(root)为叶子结点，直接删除并将空结点返回上层
delete root;
return NULL;
} else if(root->left == NULL && root->right) { // 当前结点左子树为空但右子树不空，用root的右子树替代root的位置
auto p = root->right;
delete root;
return p;
} else if(root->left && root->right == NULL) { // 当前结点右子树为空但左子树不空，用root的左子树替代root的位置
auto p = root->left;
delete root;
return p;
} else { // 当前结点左右子树都不空，把root的左子树，挂在root右子树的最左侧结点(即root的中序后继)的左子树处，再用root的右子树替代root的位置
auto q = root->right;
while(q->left != NULL) {
q = q->left;
}
q->left = root->left;
q = root->right;
delete root;
return q;
}
} else if(root->val > key) { // 当前结点不为待删除结点，将下层递归删除的结果赋给左右子树
root->left = deleteNode(root->left, key);
} else {
root->right = deleteNode(root->right, key);
}
return root;
}
};