LeetCode 450. 删除二叉搜索树中的节点-526互联

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        del(root,key);
        return root;
    }
    void del(TreeNode* &root,int key)
    {
        if(!root)   return;
        if(key<root->val)    del(root->left,key);
        else if(key>root->val)    del(root->right,key);
        else
        {
            if(!root->left&&!root->right)//叶子节点直接删除
                root=nullptr;
            else if(!root->left)    root=root->right;
            else if(!root->right)   root=root->left;
            else//有两个孩子
            {
                //寻找后继
                auto p=root->right;
                while(p->left)    p=p->left;//这里不能直接传p，传p改变不了子树
                //覆盖根节点并删除后继
                root->val=p->val;
                del(root->right,p->val);
            }

        }
    }
};