2回答

liuyubobobo

2018-11-15

已采纳

赞！完全可以：）

在这里，我希望同学们能够更加熟悉“指针”的操作，所以对于所有链式结构（包括链表），都采取不修改节点内容，而只是改变节点连接的方式完成操作：）

这一点，我在我的《玩转算法面试》课程讲链表面试题的时候有介绍。如果修改链表中节点的值，很多任务变得非常简单，不过在面试的时候，有的时候面试官会指定不让你进行这类操作：）所以，我个人认为熟悉“指针”的操作还是很有必要的。

继续加油！：）

3

1

幕布斯1098637

非常感谢！

2018-11-15

共1条回复

SsssZzzz

2018-12-05

发现跟我想的一样

不过我是因为前面删除最大最小节点时 想把删除节点的E值连同当前递归深度的节点一起返回，所以封装了一个DTO类 保存了被删除的节点的值 以及用于上层递归拼接树的节点。

所以在这一节删除任意元素时，我直接通过removeMin方法找到待删除节点的后继，然后直接把后继的值赋给待删除节点的E。

/**
 * DTO类
 * 删除节点时包装元素E值和后续节点(传给上层递归用于拼接删除元素后的树)
 */
private class RetNode {

    E e;
    Node node;

    public RetNode(E e, Node node) {
        this.e = e;
        this.node = node;
    }

}

public void remove(E e) {
        if (isEmpty()) {
            throw new IllegalArgumentException("BST is empty");
        }
        root = remove(root, e);
    }

    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e) == 0) {
//            待删除节点左子树为空
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
//            待删除节点右子树为空
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
//            待删除节点左右子树都不为空
            RetNode retNode = removeMin(node.right); //e:59 node->60
//            node的后继 直接将后继节点的值赋给当前节点
            node.e = retNode.e;
            node.right = retNode.node;
            return node;

            /*
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;
             */
        } else if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else {
            node.right = remove(node.right, e);
            return node;
        }

    }

0

1

liuyubobobo

感谢分享，继续加油！：）

2018-12-06

共1条回复