我正在尝试编写一个方法，通过给定的值从 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;
}
我可以想出一些技巧来让它返回已删除的节点，还是应该研究迭代算法(如果是这样，如果您能给我链接，我将非常感激)。
最佳答案
您不仅可以返回根，还可以返回一对根和已删除的节点(如果没有删除任何内容，则返回 null)。
您可以使用 Map.Entry 或新类来存储 2 个字段(我会推荐新类，因为它更具描述性)。
所以你可能的新签名将是 public Map.Entry<TreeNode, TreeNode> remove(TreeNode node, int data)
关于java - 从二叉搜索树中返回已删除的节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44357747/