算法数据结构

几个实现深拷贝的题目，包括使用或自定义 deepcopy 的方法

字数统计: 2k字   |   阅读时长: 9分
, , ,

摘要: 几个深拷贝的问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

今天我们看4个题，leetcode第1490题【1490. 克隆 N 叉树】，第133题【133. 克隆图】，第138题【138. 复制带随机指针的链表】，第1484题【1484. 克隆含随机指针的二叉树】。

这四个题考的都是深拷贝这个点。其中最基础的是第1490题，用 dfs 的方式实现没有环数据结构的深拷贝，其它三道题都是可能出现环的，需要在1490的方法的基础上再加一个哈希映射记录已经拷贝的节点。

1490. 克隆 N 叉树

问题

给定一棵 N 叉树的根节点 root ，返回该树的深拷贝（克隆）。

N 叉树的每个节点都包含一个值（ int ）和子节点的列表（ List[Node] ）。

1
2
3
4
class Node {
    public int val;
    public List<Node> children;
}

N 叉树的输入序列用层序遍历表示，每组子节点用 null 分隔（见示例）。

进阶：你的答案可以适用于克隆图问题吗？

算法：DFS

从根节点开始，以 DFS 的方式对各个节点进行访问，访问过程中拷贝当前访问到的节点对应的子树，访问完成后，返回拷贝的子树的根节点。

假设当前走到 node 节点，首先用 node 持有的整数值创建新的节点。而 node 还持有若干个子树的指针。我们以 DFS 的方式，递归地访问 node 的各个子树，将返回的创建好的子树的指针赋值给新节点对应持有的指针。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    Node* cloneTree(Node* root) {
        if(!root) return nullptr;
        return build(root);
    }

private:
    Node* build(Node* node)
    {
        Node *ans = new Node(node -> val);
        int m = (node -> children).size();
        (ans -> children).assign(m, nullptr);
        for(int i = 0; i < m; ++i)
        {
            Node *child = (node -> children)[i];
            if(child)
                ans -> children[i] = build(child);
        }
        return ans;
    }
};

代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def cloneTree(self, root: "Node") -> "Node":
        if root is None:
            return None
        return self.dfs(root)

    def dfs(self, node: "Node") -> "Node":
        new_node = Node(node.val)
        n_child = len(node.children)
        new_node.children = [None] * n_child
        for i, child in enumerate(node.children):
            new_node.children[i] = self.dfs(child)
        return new_node

用 copy.deepcopy

1
2
3
4
5
import copy

class Solution:
    def cloneTree(self, root: 'Node') -> 'Node':
        return copy.deepcopy(root)

自定义 __deepcopy__()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import types
import copy

def __deepcopy__(self, memo):
    if self in memo:
        return memo.get(self)
    new_root = Node(copy.deepcopy(self.val, memo)
                   ,copy.deepcopy(self.children, memo))
    memo[self] = new_root
    return new_root

class Solution:
    def cloneTree(self, root: 'Node') -> 'Node':
        if root is None:
            return None
        root.__deepcopy__ = types.MethodType(__deepcopy__, root)
        return copy.deepcopy(root)

后面3个题的思路与上面的 1490 题完全一样，也就是用 dfs 实现深拷贝，只是用哈希映射 mapping 维护已创建拷贝的节点到对应的新节点的映射，在执行创建新节点这个操作之前查看一下节点是否在哈希映射中存在，如果存在，说明前面的 dfs 的过程中已经拷贝过该节点，从哈希映射中取出对应节点即可，而不要重复创建该节点。

133. 克隆图

问题

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

1
2
3
4
class Node {
    public int val;
    public List<Node> neighbors;
}

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if(!node) return nullptr;

        unordered_map<Node*, Node*> mapping; // 已经访问过的节点

        Node *head = new Node(node -> val);
        mapping[node] = head; // DFS 之前先对点进行标记
        Node *iter = node, *iter_output = head;
        dfs(iter, iter_output, mapping);
        return head;
    }

private:
    void dfs(Node* iter, Node* iter_output, unordered_map<Node*, Node*>& mapping)
    {
        // iter 在进本次 dfs 之前已经被标记过
        // 对每一个相邻节点：
        //     若未访问过，则先建点，再连边，再 DFS 进去
        //     若已经被访问过，则直接连边(不DFS)
        for(Node *nxt: iter -> neighbors)
        {
            if(mapping.find(nxt) == mapping.end())
            {
                Node *tmp = new Node(nxt -> val);
                mapping[nxt] = tmp;
                (iter_output -> neighbors).push_back(tmp);
                dfs(nxt, tmp, mapping);
            }
            else
            {
                (iter_output -> neighbors).push_back(mapping[nxt]);
            }
        }
    }
};

代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return None
        self.mapping = dict() # 原图某节点 -> 已拷贝后的节点
        return self.dfs(node)

    def dfs(self, node: "Node") -> "Node":
        new_node = Node(node.val)
        self.mapping[node] = new_node
        n = len(node.neighbors)
        for neighbor in node.neighbors:
            if neighbor in self.mapping:
                new_node.neighbors.append(self.mapping[neighbor])
            else:
                new_node.neighbors.append(self.dfs(neighbor))
        return new_node

138. 复制带随机指针的链表

问题

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node *iter = head;
        // 第一趟遍历时，无视 random 建表, 新节点插入到原节点后面
        while(iter != nullptr)
        {
            Node *tmp = new Node(iter -> val);
            tmp -> next = iter -> next;
            iter -> next = tmp;
            iter = iter -> next -> next;
        }
        // 第二趟遍历，在原链表上处理 random 节点
        iter = head;
        while(iter != nullptr)
        {
            if(iter -> random != nullptr)
                iter -> next -> random = iter -> random -> next;
            else
                iter -> next -> random = nullptr;
            iter = iter -> next -> next;
        }
        // 第三趟遍历，分离链表
        iter = head;
        Node *dummy = new Node(0);
        Node *cur = dummy;
        while(iter != nullptr)
        {
            cur -> next = iter -> next;
            iter -> next = iter -> next -> next;
            cur = cur -> next;
            iter = iter -> next;
        }
        cur -> next = nullptr;
        return dummy -> next;
    }
};

代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if head is None:
            return None
        self.mapping = dict() # 原节点 -> 对应的已经拷贝出的节点
        return self.dfs(head)

    def dfs(self, node):
        new_node = Node(node.val)
        self.mapping[node] = new_node
        if node.next is not None:
            if node.next in self.mapping:
                new_node.next = self.mapping[node.next]
            else:
                new_node.next = self.dfs(node.next)
        if node.random is not None:
            if node.random in self.mapping:
                new_node.random = self.mapping[node.random]
            else:
                new_node.random = self.dfs(node.random)
        return new_node

1484. 克隆含随机指针的二叉树

问题

给你一个二叉树，树中每个节点都含有一个附加的随机指针，该指针可以指向树中的任何节点或者指向空（null）。

请返回该树的 深拷贝 。

该树的输入/输出形式与普通二叉树相同，每个节点都用 [val, random_index] 表示：

val：表示 Node.val 的整数
random_index：随机指针指向的节点（在输入的树数组中）的下标；如果未指向任何节点，则为 null 。
该树以 Node 类的形式给出，而你需要以 NodeCopy 类的形式返回克隆得到的树。NodeCopy 类和Node 类定义一致。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    NodeCopy* copyRandomBinaryTree(Node* root) {
        if(!root) return nullptr;
        return dfs(root);
    }

private:
    unordered_map<Node*, NodeCopy*> mapping;

    NodeCopy* dfs(Node* node)
    {
        NodeCopy *new_node = new NodeCopy(node -> val);
        mapping[node] = new_node;
        if(node -> left)
        {
            if(mapping.count(node -> left) > 0)
                new_node -> left = mapping[node -> left];
            else
                new_node -> left = dfs(node -> left);
        }
        if(node -> right)
        {
            if(mapping.count(node -> right) > 0)
                new_node -> right = mapping[node -> right];
            else
                new_node -> right = dfs(node -> right);
        }
        if(node -> random)
        {
            if(mapping.count(node -> random) > 0)
                new_node -> random = mapping[node -> random];
            else
                new_node -> random = dfs(node -> random);
        }
        return new_node;
    }
};

代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def copyRandomBinaryTree(self, root: 'Node') -> 'NodeCopy':
        if root is None:
            return None
        self.mapping = dict() # 原节点 -> 对应的已拷贝的节点
        return self.dfs(root)

    def dfs(self, node: "Node") -> "NodeCopy":
        new_node = NodeCopy(node.val)
        self.mapping[node] = new_node
        if node.left is not None:
            if node.left in self.mapping:
                new_node.left = self.mapping[node.left]
            else:
                new_node.left = self.dfs(node.left)
        if node.right is not None:
            if node.right in self.mapping:
                new_node.right = self.mapping[node.right]
            else:
                new_node.right = self.dfs(node.right)
        if node.random is not None:
            if node.random in self.mapping:
                new_node.random = self.mapping[node.random]
            else:
                new_node.random = self.dfs(node.random)
        return new_node
Share