从二进制搜索树中返回已删除的节点

Question

我正在尝试编写一个方法，该方法可以通过给定的值从BST中删除节点，并且我需要它来返回此删除的值。我发现了递归实现的各种示例，但由于它们的本质，它们不能返回删除的节点，而是返回根节点。下面是我现在

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; 
    } 

我可以拿出一些黑客攻击，使其返回删除节点，或者我应该考虑的迭代算法（如果有的话，我会很感激，如果你可以帮我介绍了链接）。

Answer 1

您不仅可以返回根，还会返回一对根和已删除的节点（如果没有删除，则返回null）。 您可以使用Map.Entry或新类来存储2个字段（我会推荐新类，因为它更具描述性）。 所以你可能的新签名将是public Map.Entry<TreeNode, TreeNode> remove(TreeNode node, int data)