Java二叉搜索树删除功能中递归辅助方法未终止的原因排查

根本原因 #

你的递归逻辑存在递归结果丢失问题，直接导致查找流程完全失效：

• 当判断目标值小于当前节点、需要去左子树查找时，你调用了getNodeToDelete(deleteKey, startingRoot.left)，但没有将这个递归调用的结果作为当前方法的返回值，递归找到的目标节点会被直接丢弃
• 当流程走到右子树的查找逻辑时，同样没有接住右子树的递归返回值，两次递归调用都是无意义的空执行
• 不管递归遍历到哪一层，代码最终都会执行return startingRoot;，返回当前层级的节点对象

结合Java递归的执行流程，最外层第一次调用getNodeToDelete时传入的startingRoot是整棵树的根节点。只要没有在匹配到目标节点时立刻返回结果、终止递归回溯，最终回到最外层时，拿到的一定是最开始传入的根节点——这完全匹配你观察到的“无论传入什么删除键，返回值永远是根节点”的现象。

举个具体的执行流程验证：假设树的根节点键值为10，左孩子键值为5，5的右孩子就是你要找的目标节点-12：

1. 第一层调用传入根节点10，判断-12 < 10，触发左子树的递归调用（传入节点5），但没有接住返回值
2. 第二层调用传入节点5，判断-12 > 5，触发右子树的递归调用（传入节点-12），同样没有接住返回值
3. 第三层调用传入节点-12，匹配到目标值，返回-12的节点对象，但因为上一层没有接住这个返回值，代码继续执行空的右子树调用，最终第二层调用返回节点5本身
4. 回到第一层调用，同样没有接住节点5的返回值，代码继续执行空的右子树调用，最终第一层调用返回根节点10，也就是最外层拿到的结果永远是根节点。

修正后的递归实现 #

核心修改点是在两个递归分支中直接返回查找结果，避免无意义的回溯：

public Node getNodeToDelete(int deleteKey, Node startingRoot) {
    // 空节点作为递归终止条件，返回null代表未找到
    if (startingRoot == null) {
        return null;
    }
    // 匹配到目标节点，立刻返回结束递归
    if (startingRoot.key == deleteKey) {
        return startingRoot;
    }
    // 目标值小于当前节点，去左子树查找，直接返回查找结果
    if (deleteKey < startingRoot.key) {
        return getNodeToDelete(deleteKey, startingRoot.left);
    }
    // 目标值大于当前节点，去右子树查找，直接返回查找结果
    return getNodeToDelete(deleteKey, startingRoot.right);
}

现有删除逻辑的潜在问题 #

修正完递归查找的问题后，你在实现删除功能时还会碰到几个逻辑坑：

• 叶节点删除逻辑中，nodeToDelete = null;没有实际效果：Java是值传递，这个操作只会把局部变量nodeToDelete置空，不会修改父节点指向该叶节点的引用，等于叶节点根本没从树上移除
• 仅靠getNodeToDelete只能拿到待删节点本身，拿不到它的父节点引用，后续不管是删除叶节点、还是调整子树连接，都没法更新父节点的左右指针，很容易出现树结构断链、节点悬空的问题
• 用右子树最小节点做值替换时，你只把待删节点的key改成了最小节点的key，没有移除原位置的最小节点，会导致树中出现重复节点、引用结构错乱的问题

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