节点删除

如果你是指 getNode 和 remove 这实际上在 BST 上走了两趟的话，是的，这两趟是可以合一的。

实际上，在之前，我们学习的使用 BST 实现的 Set，在这里就只有一趟遍历。 但是为什么 Map 我写了两趟？是因为我们的 remove 的函数设计，除了删除节点这个动作之外，还需要返回待删除节点的 Value。而我们的 remove 动作，需要返回对当前子树执行完删除操作后的新的子树的根节点。因此，我们在递归的过程中，需要记录两个值。

使用两趟遍历，其实是每一趟处理一件事情，简化了这个问题。（但损失了性能，不过整体性能依然是 logn 的）。

如果你想一趟处理，使用 getNode 找到待删除节点后，直接对这个节点做事情是不可以的。因为对待删除节点的操作，可能影响这个节点的父亲节点，所以，仅仅有这个待删除节点是不够的。（对于 BST 来说，如果有父亲节点就够了。但是，后续的 AVL 树，你会看到，一个删除动作，有可能影响待删除节点的所有祖先节点。）

(或者我不确定你的描述是不是其实你自己有思考可以如何实现，但是我没有理解。你可以尝试用代码来实现一下。这是很好的一个练习：）)

如果你想一趟解决这个问题，有两个思路：

1）在 remove 的过程中，多传入一个 Node 类型的节点，记录待删除节点。这是最简单的；

2）将 remove 的过程修改为返回两个参数。Java 原生不支持多参数函数，可以靠返回一个 Pair 来解决。

继续加油！：）