java - 从二叉搜索树中返回已删除的节点

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)