java - Java 中的深度复制

Question

我有一个Java类，Node如下:

class Node
{
    public ArrayList<Node> nbrs;
}

每个 Node 对象都包含 ArrayList nbr 中所有邻居的列表，仅此而已。

现在我需要编写一个函数:

public Node copy( Node curr )

此函数应该执行以 curr 为根的整个图的深层复制，并返回 curr 的等效副本。

我尝试在 Node 类中实现复制构造函数，如下所示:

public Node( Node n )
{
    for( Node curr : n.nbrs )
        n.nbrs.add( new Node( curr  ));
}

我现在在复制函数中复制节点 n。

但是我发现当图表包含循环时，这段代码会无限运行。

关于我应该如何克服这个问题的任何帮助。

PS:这是我 friend 面临的面试题，所以 Node 类不能再包含任何变量

Answer 1

如果 Node 类有一个父级，您就可以通过这种方式检查无限递归。但事实并非如此。因此，您需要在克隆操作期间维护一些状态，即包含当前递归到的节点的 Set 。拒绝下降到已经在 Set 中的节点。