一、包含随机指针的单链表的深度拷贝

最近遇到一道很有趣的题目：给定每个节点都包含随机指针的单链表，问如何深度拷贝这个单链表？

类似的单链表如图所示：

图1

总结了下看到的答案，大致可分为三种方法：

1、暴力复制（很朴素的方法）

因为随机指针可能指向当前节点之后的节点，所以考虑分两步来做。

第一步遍历单链表，拷贝节点及节点的next指针，不考虑节点的random指针。结束后得到一个新的单链表。

第二步遍历原单链表，如果当前访问节点A有random指针指向节点B，则在新的单链表中找到相应的节点AA以及random所指向节点BB，令AA->random = BB。

时间复杂度：O(N2)

2、通过节点映射关系实现深度拷贝

考虑第一种方法可以发现时间主要耗费在复制random指针的过程中需要查找相应的节点，因此可想到如果能够建立原单链表与新单链表节点之间的映射关系，那么只需遍历一次即可完成random指针的拷贝。详细步骤如下：

第一步遍历单链表，拷贝节点及节点的next指针，不考虑节点的random指针。结束后得到一个新的单链表。

第二步遍历原单链表，如果当前访问节点A有random指针指向节点B，则令map[A]->random = map[B]即可。

故只需要两次遍历，时间复杂度为O(2N)

代码如下：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
struct Node {
    int key;
    Node *next, *random;
    Node(int k, Node *nt, Node *rand): key(k), next(nt), random(rand) {};
};
void printInOrder(Node *node) {
    Node* curNode = node;
    while(curNode != NULL) {
        cout << "[ " << curNode->key << ", ";
        if(curNode->random == NULL) {
            cout << "NULL ] -> ";
        } else {
            cout << curNode->random->key << " ] -> ";
        }
        curNode = curNode->next;
    }
    cout << endl;
}
Node* copyLinkedList(Node* treeNode, map<Node*, Node*> *mymap) {
    if(treeNode == NULL)
        return NULL;
    Node* headNode = new Node(treeNode->key, NULL, NULL);
    Node* curNode = headNode;
    (*mymap)[treeNode] = headNode;
    treeNode = treeNode->next;
    while(treeNode != NULL) {
        Node* cloneNode = new Node(treeNode->key, NULL, NULL);
        (*mymap)[treeNode] = cloneNode;
        curNode->next = cloneNode;
        curNode = curNode->next;
        treeNode = treeNode->next;
    }
    return headNode;
}
void copyRandom(Node* treeNode, Node* cloneNode, map<Node*, Node*> *mymap) {
    Node* headNode = cloneNode;
    while(treeNode != NULL) {
        cloneNode->random = (*mymap)[treeNode->random];
        treeNode = treeNode->next;
        cloneNode = cloneNode->next;
    }
    cloneNode = headNode;
    return ;
}
Node* cloneList(Node* tree) {
    if(tree == NULL)
        return NULL;
    map<Node*, Node*> *mymap = new map<Node*, Node*>;
    Node* newList = copyLinkedList(tree, mymap);
    copyRandom(tree, newList, mymap);
    return newList;
}
int main(void) {
    Node* node1 = new Node(1, NULL, NULL);
    Node* node2 = new Node(2, NULL, NULL);
    Node* node3 = new Node(3, NULL, NULL);
    Node* node4 = new Node(4, NULL, NULL);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node1->random = node3;
    node2->random = node4;
    printInOrder(node1);
    Node* clone = cloneList(node1);
    printInOrder(clone);
    return 0;
}

3、在原单链表上插入节点并删除实现深度拷贝

基本思想同2相似，通过减少查找节点的时间来提高效率。在原单链表中每个节点之后插入一个新节点，如下图所示：

图2

当拷贝random指针时就可以通过以下代码实现。

1
2
3
4
A->next->random = A->random->next
# 恢复原单链表
A->next = A->next->next

其实这也是一种特殊的节点映射关系 。故时间复杂度同2为O(2N)

代码如下：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
using namespace std;
struct Node {
    int key;
    struct Node *next, *random;
    Node(int k, Node* nt, Node* rand): key(k), next(nt), random(rand) {};
};
// 打印链表，[a, b] 表示 key 为 a 的节点 random 指针指向 key 为 b 的节点
void printInorder(Node* node) {
    if(node == NULL)
        return ;
    cout << "[ " << node->key << " ";
    if(node->random == NULL)
        cout << "NULL ], ";
    else cout << node->random->key << " ], ";
    printInorder(node->next);
}
// 复制每个节点（不包含随机指针），并返回第一个复制的节点 
Node* copyLinkedListNode(Node* treeNode) {
    Node* curNode = treeNode;
    while(curNode != NULL) {
        Node* next = curNode->next;
        curNode->next = new Node(curNode->key, NULL, NULL);
        curNode->next->next = next;
        curNode = next;
    }
    return treeNode->next;
}
// 复制随机指针
void copyRandomNode(Node* treeNode, Node* cloneNode) {
    Node *headNode = cloneNode;
    while(treeNode != NULL) {
        if(treeNode->random != NULL)
            cloneNode->random = treeNode->random->next;
        else cloneNode->random = NULL;
        if(treeNode->next == NULL || cloneNode->next == NULL)
            return ;
        else {
            treeNode = treeNode->next->next;
            cloneNode = cloneNode->next->next;
        }
    }
    cloneNode = headNode;
}
// 恢复原来的单链表，即分离两个单链表
void restoreLinkedList(Node* treeNode, Node* cloneNode) {
    while(treeNode != NULL) {
        if(cloneNode->next != NULL) {
            Node* cloneNext = cloneNode->next->next;
            treeNode->next = treeNode->next->next;
            cloneNode->next = cloneNext;
        } else {
            treeNode->next = NULL;
        }
        treeNode = treeNode->next;
        cloneNode = cloneNode->next;
    }
    return ;
}
// 复制整个单链表
Node* cloneLinkedList(Node* treeNode) {
    if(treeNode == NULL)
        return NULL;
    Node* cloneNode = copyLinkedListNode(treeNode);
    copyRandomNode(treeNode, cloneNode);
    restoreLinkedList(treeNode, cloneNode);
    return cloneNode;
}
int main() {
    Node* node1 = new Node(1, NULL, NULL);
    Node* node2 = new Node(2, NULL, NULL);
    Node* node3 = new Node(3, NULL, NULL);
    Node* node4 = new Node(4, NULL, NULL);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node1->random = node3;
    node2->random = node4;
    cout << "traversal of original binary tree is: " << endl;
    printInorder(node1);
    Node *clone = cloneLinkedList(node1);
    cout << "\n\ntraversal of cloned binary tree is: " << endl;
    printInorder(clone);
    return 0;
}

二、包含随机指针的二叉树深度拷贝

同上，这里也有三种对应的方法。

1、暴力复制（OTZ）

就是暴力。。。时间复杂度为O(N2)

2、通过节点映射关系实现深度拷贝

同单链表中节点建立映射关系一样，这里的时间复杂度同样为O(2N)。

具体代码如下：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
struct Node {
	int key;
	Node *left, *right, *random;
	Node(int k, Node* l, Node* r, Node* rand) : key(k), left(l), right(r), random(rand) {};
};
// 按中序遍历递归打印树
// 其中[a, b]表示节点a的key值与random指针所指节点的key值
void printInorder(Node* node) {
	if(node == NULL) 
		return ;
	printInorder(node->left);
	cout << "[ " << node->key << " ";
	if(node->random == NULL) {
		cout << "NULL ], ";
	} else {
		cout << node->random->key << " ], ";
	}
	printInorder(node->right);
}
// 拷贝以treeNode为根节点的整棵树并返回拷贝完成后新的根节点
// 拷贝过程中包含所有节点的左右孩子，但不包含节点的random指针
Node* copyLeftRightNode(Node* treeNode, map<Node *, Node *> *mymap) {
	if(treeNode == NULL) {
		return NULL;
	}
	Node* cloneNode = new Node(treeNode->key, NULL, NULL, NULL);
	// 建立当前节点到克隆节点的映射
	(*mymap)[treeNode] = cloneNode;
	cloneNode->left = copyLeftRightNode(treeNode->left, mymap);
	cloneNode->right = copyLeftRightNode(treeNode->right, mymap);
	return cloneNode;
}
// 遍历并拷贝random指针
void copyRandom(Node* treeNode, Node* cloneNode, map<Node*, Node*> *mymap) {
	if(cloneNode == NULL)
		return ;
	cloneNode->random = (*mymap)[treeNode->random];
	copyRandom(treeNode->left, cloneNode->left, mymap);
	copyRandom(treeNode->right, cloneNode->right, mymap);
}
// 克隆整棵树的函数主体
Node* cloneTree(Node* tree) {
	if(tree == NULL)
		return NULL;
	// 创建节点到节点的映射
	map<Node*, Node*> *mymap = new map<Node*, Node*>;
	// 第一次遍历只拷贝树中每个节点的左右孩子
	// 也就是说暂时不拷贝random指针
	Node* newTree = copyLeftRightNode(tree, mymap);
	// 第二次遍历拷贝random指针
	copyRandom(tree, newTree, mymap);
	return newTree;
}
int main(void) {
	Node *tree = new Node(1, NULL, NULL, NULL);
	tree->left = new Node(2, NULL, NULL, NULL);
	tree->right = new Node(3, NULL, NULL, NULL);
	tree->left->left = new Node(4, NULL, NULL, NULL);
	tree->left->right = new Node(5, NULL, NULL, NULL);
	tree->random = tree->left->right;
	tree->left->right->random = tree->right;
	cout << "Inorder traversal of original binary tree is: " << endl; 
	printInorder(tree);
	Node *clone = cloneTree(tree);
	cout << "\n\nInorder traversal of cloned binary tree is: " << endl;
	printInorder(clone);
    return 0; 
}

3、在原二叉树上插入新节点后再删除

思想同单链表操作一样，但这里要注意节点间的相对关系，在创建新节点时要正确建立该节点与父节点原左右孩子的关系。具体如图示：

图3

具体代码如下：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
using namespace std;
struct Node {
	int key;
	struct Node *left, *right, *random;
	Node(int k, Node* l, Node* r, Node* rand): key(k), left(l), right(r), random(rand) {};
};
// 层次遍历
// [a, b] 表示 key 为 a 的节点 random 指针指向 key 为 b 的节点
void printInorder(Node* node) {
	if(node == NULL)
		return ;
	cout << "[ " << node->key << " ";
	if(node->random == NULL)
		cout << "NULL ], ";
	else cout << node->random->key << " ], ";
	printInorder(node->left);
	printInorder(node->right);
}
// 复制每个节点及左右孩子（不包含随机指针），并返回复制后的节点 
Node* copyLeftRightNode(Node* treeNode) {
	if(treeNode == NULL)
		return NULL;
	// 在根节点与左孩子之间插入一个新节点
	Node* left = treeNode->left;
	treeNode->left = new Node(treeNode->key, NULL, NULL, NULL);
	treeNode->left->left = left;
	if(left != NULL) {
		left->left = copyLeftRightNode(left);
	}
	// 复制后的左节点右孩子指向其父节点右孩子复制后得到的节点
	treeNode->left->right = copyLeftRightNode(treeNode->right);
	return treeNode->left;
}
// 复制随机指针
void copyRandomNode(Node* treeNode, Node* cloneNode) {
	if(treeNode == NULL)
		return ;
	if(treeNode->random != NULL)
		cloneNode->random = treeNode->random->left;
	else
		cloneNode->random = NULL;
	if(treeNode->left != NULL && cloneNode->left != NULL)
		copyRandomNode(treeNode->left->left, cloneNode->left->left);
	copyRandomNode(treeNode->right, cloneNode->right);
}
// 恢复原来的二叉树，也即分离出新复制的二叉树
// 因为右孩子关系保持正确，因此只需更新左孩子关系
void restoreTreeLeftNode(Node* treeNode, Node* cloneNode) {
	if(treeNode == NULL)
		return ;
	if(cloneNode->left != NULL) {
		Node* cloneLeft = cloneNode->left->left;
		treeNode->left = treeNode->left->left;
		cloneNode->left = cloneLeft;
	}
	else
		treeNode->left = NULL;
	restoreTreeLeftNode(treeNode->left, cloneNode->left);
	restoreTreeLeftNode(treeNode->right, cloneNode->right);
}
// 复制整棵二叉树
Node* cloneTree(Node* treeNode) {
	if(treeNode == NULL)
		return NULL;
	Node* cloneNode = copyLeftRightNode(treeNode);
	copyRandomNode(treeNode, cloneNode);
	restoreTreeLeftNode(treeNode, cloneNode);
	return cloneNode;
}
int main() {
/*
	Node* tree = new Node(1);
	tree->left = new Node(2);
	tree->right = new Node(3);
	tree->left->left = new Node(4);
	tree->left->right = new Node(5);
	tree->random = tree->left->right;
	tree->left->left->random = tree;
	tree->left->right->random = tree->right;
*/
	Node *tree = new Node(10, NULL, NULL, NULL);
    Node *n2 = new Node(6, NULL, NULL, NULL);
    Node *n3 = new Node(12, NULL, NULL, NULL);
    Node *n4 = new Node(5, NULL, NULL, NULL);
    Node *n5 = new Node(8, NULL, NULL, NULL);
    Node *n6 = new Node(11, NULL, NULL, NULL);
    Node *n7 = new Node(13, NULL, NULL, NULL);
    Node *n8 = new Node(7, NULL, NULL, NULL);
    Node *n9 = new Node(9, NULL, NULL, NULL);
    tree->left = n2;
    tree->right = n3;
    tree->random = n2;
    n2->left = n4;
    n2->right = n5;
    n2->random = n8;
    n3->left = n6;
    n3->right = n7;
    n3->random = n5;
    n4->random = n9;
    n5->left = n8;
    n5->right = n9;
    n5->random = tree;
    n6->random = n9;
    n9->random = n8;
	cout << "traversal of original binary tree is: " << endl;
	printInorder(tree);
	Node *clone = cloneTree(tree);
	cout << "\n\ntraversal of cloned binary tree is: " << endl;
	printInorder(clone);
	return 0;
}