我有一个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 类不能再包含任何变量
最佳答案
如果 Node 类有一个父级
,您就可以通过这种方式检查无限递归。但事实并非如此。因此,您需要在克隆操作期间维护一些状态,即包含当前递归到的节点的 Set
。拒绝下降到已经在 Set
中的节点。
关于java - Java 中的深度复制,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9870236/