---
tags: leetcode
---

# [1490. Clone N-ary Tree](https://leetcode.com/problems/clone-n-ary-tree/)
---
# My Solution
## Solution 1
### The Key Idea for Solving This Coding Question
DFS
### C++ Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    Node* cloneTree(Node *root) {
        if (root == nullptr) {
            return nullptr;
        }

        Node *newNode = new Node(root->val);
        for (Node *next : root->children) {
            newNode->children.push_back(cloneTree(next));
        }

        return newNode;
    }
};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the n-ary tree referred by `root`.
### Space Complexity
$O(H)$
$H$ is the height of the n-ary tree referred by `root`.
## Solution 2
### The Key Idea for Solving This Coding Question
BFS
### C++ Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

struct nodeData {
    Node *original;
    Node *cloned;
    nodeData(Node *original, Node *cloned) : original(original), cloned(cloned) {}
};

class Solution {
public:
    Node *cloneTree(Node *root) {
        if (root == nullptr) {
            return nullptr;
        }
        
        Node *clonedRoot = new Node(root->val);
        queue<nodeData> q;
        
        q.push(nodeData(root, clonedRoot));
        while (!q.empty()) {
            nodeData curr = q.front();
            q.pop();
            
            for (Node *nextOriginal : curr.original->children) {
                Node *nextCloned = new Node(nextOriginal->val);
                curr.cloned->children.push_back(nextCloned);
                q.push(nodeData(nextOriginal, nextCloned));
            }
        }
        
        return clonedRoot;
    }
};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the n-ary tree referred by `root`.
### Space Complexity
$O(n)$
$n$ is the number of nodes in the n-ary tree referred by `root`.
# Miscellane
<!--
# Test Cases

[1,null,3,2,4,null,5,6]

[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

-->