面试题：C++ 中实现二叉树节点删除操作

Question

请使用C++ 实现二叉树节点的删除功能。假设二叉树节点结构如下： ```cpp struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; ``` 编写一个函数 `TreeNode* deleteNode(TreeNode* root, int key)`，该函数用于删除二叉搜索树中值为 `key` 的节点，并返回删除节点后的二叉搜索树的根节点。需考虑多种情况，如删除节点为叶节点、只有一个子节点、有两个子节点等情况。

Answer 1

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

    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        } else {
            TreeNode* minNode = root->right;
            while (minNode->left != nullptr) {
                minNode = minNode->left;
            }
            root->val = minNode->val;
            root->right = deleteNode(root->right, minNode->val);
        }
    }
    return root;
}