面试题：C语言中二叉树节点删除的实现

Question

在C语言中，给定一个二叉树，编写一个函数来删除指定值的节点。要求考虑多种情况，比如删除的节点是叶子节点、有一个子节点或有两个子节点。假设二叉树节点结构如下： ```c struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; ```

Answer 1

struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    if (root == NULL) {
        return root;
    }

    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) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        // 情况2：节点有两个子节点
        struct TreeNode* temp = root->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}