golang 解法, 执行用时: 8 ms, 内存消耗: 6.3 MB, 提交时间: 2023-10-16 21:36:34

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func cloneTree(root *Node) *Node {
	 if root == nil {
        return nil
    }
    
    node := &Node{Val:root.Val, Children: []*Node{}}
    
    for _, child := range root.Children {
        node.Children = append(node.Children, cloneTree(child))
    }
    return node
}

java 解法, 执行用时: 0 ms, 内存消耗: 44.9 MB, 提交时间: 2023-10-16 21:30:27

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

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

class Solution {
    public Node cloneTree(Node root) {
        if (root == null) {
            return null;
        }
        Node node = new Node(root.val);
        for (int i = 0; i < root.children.size(); i++) {
            node.children.add(cloneTree(root.children.get(i)));
        }
        return node;
    }
}

javascript 解法, 执行用时: 96 ms, 内存消耗: 48.5 MB, 提交时间: 2023-10-16 21:29:52

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val === undefined ? 0 : val;
 *    this.children = children === undefined ? [] : children;
 * };
 */

/**
 * @param {Node|null} node
 * @return {Node|null}
 */
var cloneTree = function(root) {
    return JSON.parse(JSON.stringify(root));
};

cpp 解法, 执行用时: 44 ms, 内存消耗: 171.4 MB, 提交时间: 2023-10-16 21:29:04

/*
// 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) {
        //////////// dfs最简单
        if (root == NULL)
            return NULL;
        Node * rt = new Node(root->val);
        for (Node * ch: root->children) {
            rt->children.push_back(cloneTree(ch));
        }
        return rt;
    }
    
    Node* cloneTree2(Node* root) {
        if (root == NULL)
            return NULL;
        
        Node * rt = new Node(root->val);
        //////////////////// bfs 简单思路
        queue<Node *> q1, q2;
        q1.push(root);
        q2.push(rt);

        while (q1.size()) {
            Node * cur1 = q1.front();   q1.pop();
            Node * cur2 = q2.front();   q2.pop();
            for (Node * ch: cur1->children) {
                q1.push(ch);
                Node * tmp = new Node(ch->val);
                cur2->children.push_back(tmp);
                q2.push(tmp);
            }
        }
        return rt;
    }
};

python3 解法, 执行用时: 72 ms, 内存消耗: 20.2 MB, 提交时间: 2023-10-16 21:27:38

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""

class Solution:
    def cloneTree(self, root: 'Node') -> 'Node':
        ########## dfs最简单
        if root == None:
            return None
        rt = Node(root.val)
        for ch in root.children:
            rt.children.append(self.cloneTree(ch))
        return rt
        
    def cloneTree2(self, root: 'Node') -> 'Node':
        ########## bfs
        if root == None:
            return None
        rt = Node(root.val)

        q1 = [root]
        q2 = [rt]
        while q1:
            cur1 = q1.pop(0)
            cur2 = q2.pop(0)
            for ch in cur1.children:
                q1.append(ch)

                tmp = Node(ch.val)
                cur2.children.append(tmp)
                q2.append(tmp)

        return rt
        

    def cloneTree3(self, root: 'Node') -> 'Node':
        ### 递归
        if root:
            return Node(root.val, list(map(self.cloneTree3, root.children)))