Java二进制搜索树删除递归返回删除元素

Question

这是我目前的代码。我不知道如何返回删除的元素。现在它正在返回新的树根。你们能提供一些建议吗？谢谢

public SomeDataType remove(String key) {
    Node removed = remove(root, key);
    if (removed != null){
        return removed.data;
    }
    return null;
}
// TO DO: RETURN REMOVED NODE
private Node remove(Node n, String key) {
    if (n == null) {
        return null;
    }
    else if (n.data.getKey().compareTo(key) < 0){
        n.right = remove(n.right, key);
    }
    else if (n.data.getKey().compareTo(key) > 0){
        n.left = remove(n.left, key);
    }
    else{
        if (n.right != null){
            SomeDataType successor = leftMost(n.right).data;
            n.data = successor;
            n.right = remove(n.right, successor.getKey()); 
        }
        else{
            n = n.left;
        }
    }
    return n;
}
private Node leftMost(Node n) {
    if (n.left == null){
        return n;
    }
    else{
        return leftMost(n.left);
    }
}

Answer 1

在包装器方法中创建一个变量来保存密钥，然后返回它。

public SomeDataType remove(String key) {
    E data = key //E is a generic data type
    Node removed = remove(root, key);
    if (removed != null){
        return data;
    }
    return null;