题目大意：
Given a root of an N-ary tree, return a deep copy (clone) of the tree.
Each node in the n-ary tree contains a val (int) and a list (List[Node]) of its children.
class Node {
public int val;
public List<Node> children;
}
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Follow up: Can your solution work for the graph problem?
Example 1:
Input: root = [1,null,3,2,4,null,5,6] Output: [1,null,3,2,4,null,5,6]
Example 2:
Input: root = [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] Output: [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]
Constraints:
- The depth of the n-ary tree is less than or equal to
1000. - The total number of nodes is between
[0, 10^4].
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1490
解题思路分析：
这道题考查的是深度拷贝，在java语言中，使用等号赋值实际上只是地址（指针）拷贝，并不能实现深度拷贝的效果。因此对于每个节点对象我们都必须重新new一个新的对象，然后将原节点的每个参数赋值到新的节点中。
解题时，我们使用dfs递归方式遍历树中每一个节点，首先new一个新的节点对象用于拷贝当前节点，将新的节点值设置为原节点值。另外新建一个子节点列表，递归当前节点的每一个子节点，递归返回值（拷贝后的子节点）加入到新建的子节点列表中。最后将该列表赋值到新建节点的列表对象。当前递归的返回值为该新建节点。
实现代码：
public Node cloneTree(Node root) {
if(root==null) return null; // 如果节点为空，返回空
Node node = new Node(); // 新建一个节点对象
node.val=root.val; // 设置新的节点值为元节点值
List<Node> children=new ArrayList<>(); // 新建子节点列表
for(Node c : root.children){ // 循环每一个子节点
// 递归拷贝每一个子节点，并将其加入新建子节点列表
children.add(cloneTree(c));
}
// 设置拷贝后的子节点列表
node.children = children;
// 返回当前新建的节点对象
return node;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Clone N-ary Tree.
Memory Usage: 41.2 MB, less than 100.00% of Java online submissions for Clone N-ary Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1490-clone-n-ary-tree-解题思路分析/