如何在二叉搜索树中去除重复节点？求C语言实现解决方案

别慌，处理二叉搜索树（BST）的重复节点其实有两种比较容易上手的思路，我给你一步步拆解，再附上C语言的实现示例，应该能帮你走出困境～

1. 原地修改法（直接在原树上删除重复节点） #

这个思路的核心是利用BST的特性：重复值的节点一定在当前节点的右子树中（因为中序遍历是有序的，相同值会连续出现）。我们可以遍历每个节点，删除其右子树中所有和它值相同的节点。

步骤拆解 #

• 先实现一个BST节点的删除函数（这是BST操作的基础，处理三种删除场景：叶子节点、单子女节点、双子女节点）
• 然后递归遍历每个节点，清理其右子树中的重复值节点

代码示例 #

#include <stdlib.h>

// 定义BST节点结构
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 辅助函数：删除BST中指定值的节点，返回删除后的根节点
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) return NULL;

    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        // 情况1：当前节点是叶子节点
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        // 情况2：只有一个子节点
        else if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // 情况3：有两个子节点，找右子树的最小节点替代当前节点
        TreeNode* minNode = root->right;
        while (minNode->left != NULL) {
            minNode = minNode->left;
        }
        root->val = minNode->val;
        root->right = deleteNode(root->right, minNode->val);
    }
    return root;
}

// 辅助函数：递归遍历并删除重复节点
void removeDuplicatesHelper(TreeNode* root) {
    if (root == NULL) return;

    // 删除当前节点右子树中所有和当前节点值相同的节点
    while (root->right != NULL && root->right->val == root->val) {
        root->right = deleteNode(root->right, root->val);
    }

    // 递归处理左子树和清理后的右子树
    removeDuplicatesHelper(root->left);
    removeDuplicatesHelper(root->right);
}

// 主函数：去除BST中的重复节点
TreeNode* removeDuplicates(TreeNode* root) {
    removeDuplicatesHelper(root);
    return root;
}

2. 中序遍历+重建BST法（更直观，适合新手） #

这个方法逻辑更简单：利用BST中序遍历的有序性，先收集所有不重复的节点值，再用这些值重建一棵新的BST。

步骤拆解 #

• 中序遍历原BST，收集所有唯一值（跳过重复值）
• 用分治法把有序的唯一值数组转换成平衡BST

代码示例 #

#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 辅助函数：中序遍历收集唯一值
void inorderCollect(TreeNode* root, int* values, int* size) {
    if (root == NULL) return;

    inorderCollect(root->left, values, size);
    // 只添加不重复的值
    if (*size == 0 || values[*size - 1] != root->val) {
        values[*size] = root->val;
        (*size)++;
    }
    inorderCollect(root->right, values, size);
}

// 辅助函数：有序数组转BST
TreeNode* sortedArrayToBST(int* nums, int start, int end) {
    if (start > end) return NULL;

    int mid = start + (end - start) / 2;
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = nums[mid];
    newNode->left = sortedArrayToBST(nums, start, mid - 1);
    newNode->right = sortedArrayToBST(nums, mid + 1, end);
    return newNode;
}

// 主函数：去重并重建BST
TreeNode* removeDuplicates(TreeNode* root) {
    if (root == NULL) return NULL;

    // 收集唯一值（这里假设节点数不超过1000，实际可以用动态数组）
    int uniqueVals[1000];
    int size = 0;
    inorderCollect(root, uniqueVals, &size);

    // 重建BST
    return sortedArrayToBST(uniqueVals, 0, size - 1);
}

• 内存管理：两种方法中，删除或替换节点时都要记得用free()释放内存，避免内存泄漏；如果用重建法，原BST的内存需要手动遍历释放（如果不需要保留原树的话）。
• 边界测试：测试空树、所有节点值都相同的树、只有单个节点的树等极端情况，确保函数鲁棒性。

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