algorithm - 如何复制包含循环的完整非二叉树

Question

请与我分享您对复制完整非二叉树这个问题的想法和任何解决方案，它可能还包括一些子节点连接到其他父节点的循环。

例子:
在这里，“A”是根或父级，它的子级像往常一样是“B”和“C”，最后，子级“G”连接回其祖父级别“B”，类似地“I”连接到它的直接父“C”，所以这些就像一个循环，这也需要按原样复制到新树中。因此，这里我们需要额外的逻辑来识别循环，同时复制子节点，并且不会陷入无限循环，并最终返回整棵树的副本。

A
 - B
   - D
   - E
     - F
     - G --> B
 - C
   - I --> C
   - K

这个类或者节点结构可以是这样的:

public class Node{
  private String value;
  private List<Node> childrens;

  public Node copyTree(Node root) {
    ...
    //return
  }
}

感谢我们的帮助。

Answer 1

我认为最直接的方法是从已复制到其副本的节点中保留 map 。然后在制作节点的新副本之前检查 map 。像这样的东西(未经测试)应该可以工作:

public static Node copyTree(Node root) {
    return copyTree(root, new HashMap<>());
}

private static Node copyTree(Node root, Map<Node, Node> images) {
    Node copy = images.get(root);
    if (copy == null) {
        copy = new Node();

        // register the copy before recursing on children
        images.put(root, copy);

        // now fill in the copy
        copy.value = root.value;
        copy.children = new ArrayList<>();
        for (Node child : root.children) {
            copy.children.add(copyTree(child, images);
        }
    }
    return copy;
}