求助：基于BST特性设计符合要求的递归节点删除算法

你的原代码问题在于没有利用BST左子树键值均小于根、右子树键值均大于根的核心特性，导致做了很多不必要的子树遍历。结合深度限制和BST特性，我们可以通过剪枝大幅减少递归次数，同时满足“无全局变量/引用传递”的要求。

核心思路 #

我们要找的是深度≥x且键值<k的最大节点，结合BST特性可以推导：

1. 键值<k的最大节点，优先出现在右子树（因为右子树键值更大）；
2. 若当前节点键值≥k，其右子树所有节点必然≥k，直接跳过右子树递归；
3. 深度未达x时，当前节点本身不满足条件，只能去子树中寻找；深度达标后，直接在当前子树内按BST规则找符合键值要求的最大节点。

优化后的代码实现 #

typedef struct Node {
    int key;
    struct Node *sx; // 左子树
    struct Node *dx; // 右子树
} Node;

#define NIL NULL

// 递归函数：在以T为根的子树中，寻找深度≥dis且键值<k的最大节点，返回该节点（NIL表示未找到）
Node* findTarget(Node* T, int x, int k, int dis) {
    if (T == NIL) return NIL;

    if (dis < x) {
        Node* rightResult = NIL;
        // 当前节点键值<k时，右子树可能存在更大的符合条件的节点，优先递归右子树
        if (T->key < k) {
            rightResult = findTarget(T->dx, x, k, dis + 1);
        }
        // 右子树找到结果直接返回，否则递归左子树
        return rightResult != NIL ? rightResult : findTarget(T->sx, x, k, dis + 1);
    } else {
        // 深度达标，按BST规则找键值<k的最大节点
        if (T->key >= k) {
            // 当前节点键值≥k，只能去左子树寻找
            return findTarget(T->sx, x, k, dis + 1);
        } else {
            // 当前节点键值<k，先检查右子树是否有更大的符合条件的节点
            Node* rightResult = findTarget(T->dx, x, k, dis + 1);
            // 右子树有结果则返回，否则当前节点就是当前子树的最优解
            return rightResult != NIL ? rightResult : T;
        }
    }
}

Node* Algo(Node* T, int x, int k) {
    Node* target = findTarget(T, x, k, 0);
    if (target != NIL) {
        T = delete(T, target->key); // 调用标准BST删除节点算法
    }
    return T;
}

关键优化点说明 #

• 剪枝无效子树：当当前节点键值≥k时，直接跳过右子树递归（因为BST右子树键值都≥当前节点，必然≥k），避免无意义的遍历；
• 优先递归右子树：当当前节点键值<k时，优先递归右子树（右子树键值更大，更可能是我们要找的最大节点），减少不必要的左子树递归；
• 深度与键值逻辑结合：深度未达标时，只递归子树；深度达标后，直接在当前子树内按BST特性筛选节点，无需调用通用的Predecessor函数（原代码的Predecessor未考虑深度限制，且效率更低）。

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