无需递归和额外函数的BST节点删除实现及递归逻辑优化

方案1：无递归、无额外函数的BST删除实现 #

思路：通过迭代定位待删除节点及其父节点，再根据节点子节点数量分类处理，所有逻辑封装在单个函数内，无递归调用、无额外辅助函数。
完整实现代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode *cur = root, *parent = nullptr;
        // 迭代查找待删除节点和父节点
        while (cur != nullptr && cur->val != key) {
            parent = cur;
            cur = cur->val < key ? cur->right : cur->left;
        }
        // 未找到目标节点直接返回
        if (cur == nullptr) return root;

        // 处理待删除节点只有0/1个子节点的情况
        if (cur->left == nullptr) {
            TreeNode* child = cur->right;
            if (parent == nullptr) root = child;
            else parent->left == cur ? parent->left = child : parent->right = child;
            delete cur;
        } else if (cur->right == nullptr) {
            TreeNode* child = cur->left;
            if (parent == nullptr) root = child;
            else parent->left == cur ? parent->left = child : parent->right = child;
            delete cur;
        } 
        // 处理待删除节点左右子节点都存在的情况
        else {
            TreeNode *minParent = cur, *minNode = cur->right;
            while (minNode->left != nullptr) {
                minParent = minNode;
                minNode = minNode->left;
            }
            cur->val = minNode->val;
            minParent->left == minNode ? minParent->left = minNode->right : minParent->right = minNode->right;
            delete minNode;
        }
        return root;
    }
};

方案2：移除while循环的纯递归实现（无额外自定义函数） #

思路：通过给原deleteNode函数增加默认参数的方式，复用递归框架实现原while循环的「查找右子树最小节点并挂载左子树」逻辑，不需要新增任何自定义辅助函数，完全符合要求。
修改后的完整代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 新增默认参数insertLeft：当不为空时，递归将该子树挂载到当前子树的最左节点
    TreeNode* deleteNode(TreeNode* r, int k, TreeNode* insertLeft = nullptr) {
        // 挂载逻辑分支
        if (insertLeft != nullptr) {
            if (r == nullptr) return insertLeft;
            r->left = deleteNode(r->left, 0, insertLeft);
            return r;
        }
        // 原有删除逻辑
        if(r == nullptr)
            return nullptr;
        if(r->val < k)
        {
            r->right = deleteNode(r->right, k);
            return r;
        }
        else if(r->val > k)
        {
            r->left = deleteNode(r->left, k);
            return r;
        }
        if(r->left == nullptr)
            return r->right;
        if(r->right == nullptr)
            return r->left;        
        // 原while逻辑替换为递归调用，将左子树挂载到右子树最左节点
        r->right = deleteNode(r->right, 0, r->left);
        return r->right;
    }
};

代码说明：外部调用方式和原有实现完全一致，不需要传第三个参数，默认值为空时走正常删除逻辑；需要挂载左子树时传入第三个参数，自动递归查找最左节点完成挂载，完全替换了原来的while循环逻辑。

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