Skip to content

1490. Clone N-ary Tree 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  Node* cloneTree(Node* root) {
    if (root == nullptr)
      return nullptr;
    if (const auto it = map.find(root); it != map.cend())
      return it->second;

    Node* newNode = new Node(root->val);
    map[root] = newNode;

    for (Node* child : root->children)
      newNode->children.push_back(cloneTree(child));

    return newNode;
  }

 private:
  unordered_map<Node*, Node*> map;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public Node cloneTree(Node root) {
    if (root == null)
      return null;
    if (map.containsKey(root))
      return map.get(root);

    Node newNode = new Node(root.val);
    map.put(root, newNode);

    for (Node child : root.children)
      newNode.children.add(cloneTree(child));

    return newNode;
  }

  private Map<Node, Node> map = new HashMap<>();
}