题目描述：
给定一棵 N 叉树的根节点 root ，返回该树的深拷贝（克隆）。
N 叉树的每个节点都包含一个值（ int ）和子节点的列表（ List[Node] ）。
class Node {
public int val;
public List children;
}
N 叉树的输入序列用层序遍历表示，每组子节点用 null 分隔（见示例）
示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[1,null,3,2,4,null,5,6]

示例 2：
输入：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]
输出：[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]

提示：
给定的 N 叉树的深度小于或等于 1000。
节点的总个数在 [0, 10^4] 之间

方法1:
主要思路：解题链接汇总
（1）dfs；
（2）扩展二叉树的先序遍历；

/*
// 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:
    void dfs(Node* root,Node* new_root){
        if(root==NULL){
            return;
        }
        for(int i=0;i<root->children.size();i++){//先序遍历
            Node* tmp = new Node(root->children[i]->val);
            new_root->children.push_back(tmp);
            dfs(root->children[i],tmp);
        }
        return;
    }
    Node* cloneTree(Node* root) {
        if(root==NULL){
            return NULL;
        }
        Node* new_root = new Node(root->val);//初始跟节点
        dfs(root,new_root);
        return new_root;
    }
};

//go语言实现

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func dfs(root,new_root *Node) {
    if root==nil {
        return 
    }
    for i:=0;i<len(root.Children);i++ {
        tmp := new(Node)
        tmp.Val = root.Children[i].Val
        new_root.Children = append(new_root.Children,tmp)
        dfs(root.Children[i],tmp)
    }
    return
}
func cloneTree(root *Node) *Node {
	if root==nil {
        return nil
    }
    new_root := new(Node)
    new_root.Val = root.Val
    dfs(root,new_root)
    return new_root
}