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

Question

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

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

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

这个class或者节点结构可以是这样的：

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

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

感谢我们的帮助。

Answer 1

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

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;
}

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

How To Copy A Full Non-Binary Tree Including Loops

algorithm

tree

binary-tree

graph

data-structures