力扣题解450、删除二叉搜索树中的节点

交换后继节点

struct TreeNode *find_succ(struct TreeNode *root) { //找到这棵树的最小值
    while (root->left) {
        root = root->left;
    }
    return root;
}

struct TreeNode* deleteNode(struct TreeNode* root, int key){
    if (root == NULL) return NULL;
    if (root->val > key) {
        root->left = deleteNode(root->left, key);
    } else if (root->val < key) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL || root->right == NULL) { //这个节点出度为0或者为1，直接删除
            struct TreeNode *tmp = root->left ? root->left : root->right;
            free(root);
            return tmp;
        }
        struct TreeNode *temp = find_succ(root->right); //找到后继节点
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val); //删除后继节点
        
    }
    return root;
}

交换前驱节点

struct TreeNode *find_succ(struct TreeNode *root) { //找到这棵树的最小值
    while (root->right) {
        root = root->right;
    }
    return root;
}

struct TreeNode* deleteNode(struct TreeNode* root, int key){
    if (root == NULL) return NULL;
    if (root->val > key) {
        root->left = deleteNode(root->left, key);
    } else if (root->val < key) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL || root->right == NULL) { //这个节点出度为0或者为1，直接删除
            struct TreeNode *tmp = root->left ? root->left : root->right;
            free(root);
            return tmp;
        }
        struct TreeNode *temp = find_succ(root->left); //找到前驱节点
        root->val = temp->val;
        root->left = deleteNode(root->left, temp->val); //在左子树删除前驱节点
        
    }
    return root;
}