1490 克隆 N 叉树

题目描述:
给定一棵 N 叉树的根节点 root ,返回该树的深拷贝(克隆)。
N 叉树的每个节点都包含一个值( int )和子节点的列表( List[Node] )。
class Node {
public int val;
public List children;
}
N 叉树的输入序列用层序遍历表示,每组子节点用 null 分隔(见示例)
示例 1:
1490 克隆 N 叉树
输入:root = [1,null,3,2,4,null,5,6]
输出:[1,null,3,2,4,null,5,6]

示例 2:
1490 克隆 N 叉树输入: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
}
上一篇:扁平数据结构转Tree


下一篇:侧边分类导航滚动以及购物车