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;