xstruct 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;
}
xxxxxxxxxx
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;
}