如何在Java中实现惰性删除二叉搜索树的findMinimum方法

嘿，针对你这个带惰性删除的二叉搜索树findMin实现问题，我来给你捋清楚思路和具体代码～

常规BST的findMin是直接找最左叶子，但惰性删除下，这个节点可能已经被标记为deleted=true，所以我们需要调整逻辑：优先在左子树找未被删除的最小节点，如果左子树全删了，再检查当前节点，最后去右子树找。本质是遍历所有未被删除的节点，找到其中值最小的那个。

先明确你的TreeNode大概是这样的（如果有差异可以对应调整）：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    boolean deleted; // 惰性删除标记

    TreeNode(int val) {
        this.val = val;
        this.deleted = false;
    }
}

递归版本逻辑清晰，容易理解：

public TreeNode findMin(TreeNode root) {
    if (root == null) {
        return null; // 空树或子树无有效节点
    }

    // 1. 先递归查找左子树的最小有效节点
    TreeNode leftMin = findMin(root.left);
    if (leftMin != null) {
        return leftMin;
    }

    // 2. 左子树没有有效节点，检查当前节点是否有效
    if (!root.deleted) {
        return root;
    }

    // 3. 当前节点已删除，递归查找右子树的最小有效节点
    return findMin(root.right);
}

逻辑验证（对应你的例子） #

假设原树结构是：

• 根节点20，左孩子5，右孩子25
• 节点5的右孩子17

当你标记20、5、17为deleted=true后：

1. 调用findMin(20)，先递归左子树findMin(5)
2. findMin(5)递归左子树（null），返回null；检查节点5已删除，递归右子树findMin(17)
3. findMin(17)递归左子树（null），返回null；检查节点17已删除，递归右子树（null），返回null
4. 回到findMin(20)，左子树返回null；检查节点20已删除，递归右子树findMin(25)
5. findMin(25)递归左子树（null），返回null；检查节点25未删除，返回25
   最终结果就是25，完全符合你的需求～

如果树的深度很大，递归可能导致栈溢出，迭代版本更安全高效：

public TreeNode findMinIterative(TreeNode root) {
    TreeNode current = root;
    while (current != null) {
        // 先走到当前子树的最左节点
        while (current.left != null) {
            current = current.left;
        }

        // 检查这个最左节点是否有效
        if (!current.deleted) {
            return current;
        }

        // 最左节点已删除，往右子树继续查找
        current = current.right;
    }
    // 所有节点都已删除，返回null
    return null;
}

可以封装一个辅助函数，用来快速判断节点是否有效，让代码更简洁：

private boolean isActive(TreeNode node) {
    return node != null && !node.deleted;
}

比如在递归版本里，可以用if (isActive(leftMin))来替代判断，可读性更好。

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