二叉搜索树删除奇数节点代码问题排查

你的代码存在两个关键问题，导致删除奇数节点后出现异常（比如重复节点、未正确清理目标节点）：

1. 替换节点值后错误复用删除奇数节点的递归函数 #

当当前节点是奇数且有左右子树时，你用右子树的最小节点值替换当前节点值后，调用了remove_odd_nodes(root->right)——这个函数的作用是删除右子树中的奇数节点，但我们现在需要删除的是那个已经被复制值的min_node（它是偶数，不会被remove_odd_nodes处理），这会导致右子树中保留重复的键值，同时重复递归处理已经清理过的子树。

2. 未正确删除右子树中的最小节点 #

因为min_node的值已经被复制到当前root节点，我们需要从右子树中删除这个min_node，而不是再次扫描整个右子树删除奇数节点。

修复后的代码 #

struct Node* delete_min_node(struct Node* root) {
    if (root->left == NULL) {
        struct Node* temp = root->right;
        free(root);
        return temp;
    }
    root->left = delete_min_node(root->left);
    return root;
}

struct Node* remove_odd_nodes(struct Node* root) {
    if (root == NULL) {
        return NULL;
    }
    root->left = remove_odd_nodes(root->left);
    root->right = remove_odd_nodes(root->right);
    
    if (root->value % 2 == 1) {
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        }
        if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
        // 找到右子树最小节点
        struct Node* min_node = root->right;
        while (min_node->left != NULL) {
            min_node = min_node->left;
        }
        // 替换当前节点值
        root->value = min_node->value;
        // 删除右子树中的最小节点，而非重新处理整个右子树
        root->right = delete_min_node(root->right);
    }
    return root;
}

修复说明 #

• 新增delete_min_node辅助函数，专门用于删除二叉搜索树中的最小节点，这是二叉搜索树删除节点的标准操作。
• 替换节点值后，调用delete_min_node清理右子树中的原min_node，避免重复节点，同时保证递归逻辑的正确性。

内容的提问来源于stack exchange，提问作者marianaUser01