### 解题思路
要删除的节点分为三种情况
1.节点既没有左子树也没有右子树:直接删除即可
2.节点只有左子树或者右子树:用子节点替换即可
3.既有左子树又有右子树:找到该节点的后继(比该节点大的最小数),替换后递归删除后继
### 代码
class Solution {
public:
void delNode(TreeNode* &root,int val){ //加引用可以直接操作节点
if(!root) return;
if(root->val == val){
if(!root->left && !root->right) root = nullptr; //没有左子节点和右子节点,直接删除
else if(!root->left) root = root->right; //用子树覆盖
else if(!root->right) root = root->left; //用子树覆盖
else{ //找前驱
TreeNode* p = root->right;
while(p->left) p = p->left; //找前驱
root->val = p->val;
delNode(root->right,p->val);
}
}
else if(root->val < val) delNode(root->right,val);
else delNode(root->left,val);
}
TreeNode* deleteNode(TreeNode* root, int key) {
delNode(root,key);
return root;
}
};