Gelöschten Knoten aus dem binären Suchbaum zurückgeben

Question

Ich versuche, eine Methode zu schreiben, die Knoten aus BST um den angegebenen Wert entfernen würde, und ich brauche es, um diesen gelöschten Wert zurückzugeben. Ich habe verschiedene Beispiele für rekursive Implementierungen gefunden, aber aufgrund ihrer Natur können sie keinen gelöschten Knoten, sondern den Root zurückgeben. Hier ist, was ich habe jetzt

public TreeNode remove(TreeNode node, int data) { 
     if (null == node) { 
      return null; 
     } 
     if (data < node.st.getkey()) { 
      node.left = remove(node.left, data); 
     } else if (data > node.st.getkey()) { 
      node.right = remove(node.right, data); 
     } else { // case for equality 

      if (node.left != null && node.right != null) { 
       TreeNode minInRightSubTree = min(node.right); 

       copyData(node , minInRightSubTree); 

       node.right = remove(node.right, minInRightSubTree.st.getkey()); 
      } else { 
       if (node.left == null && node.right == null) { 
        node = null; 
       } else {// one child case 
        TreeNode deleteNode = node; 
        node = (node.left != null) ? (node.left) : (node.right); 
        deleteNode = null; 
       } 
      } 
     } 
     return node; 
    } 

Kann ich kommen mit einigen Hack, um es gelöscht Knoten zu machen zurückzukehren, oder sollte ich in iterativen Algorithmus (und wenn ja, würde ich es wirklich schätzen, wenn Sie könnte mich mit dem Link anschließen).

Answer 1

Sie können nicht nur root, sondern auch ein Root- und einen gelöschten Knoten (oder null, wenn nichts gelöscht wurde) zurückgeben. Sie können Map.Entry oder neue Klasse verwenden, um 2 Felder zu speichern (ich würde eine neue Klasse empfehlen, da sie beschreibender ist). So ist Ihre mögliche neue Signatur public Map.Entry<TreeNode, TreeNode> remove(TreeNode node, int data)