05 August 2008
给出一棵二叉树，使得每个节点都包含一个额外的随机指针，该指针可以指向树中的任何节点或为空。
返回树的深层副本。
该树以与普通二叉树相同的输入/输出方式表示，其中每个节点表示为一对 [val, random_index] 其中：
val：表示 Node.val 的整数 random_index：随机指针指向的节点（在输入中）的索引，如果它不指向任何节点，则为 null。 您将在 Node 类中获得树，并且您应该在 NodeCopy 类中返回克隆的树。 NodeCopy 类只是具有相同属性和构造函数的 Node 类的克隆。
DFS
Use a map to record coresponding relationship between original node and copy node
Use dfs, for every node and random node, check whether we created it before.
TC: O(N), SC O(N), n is nodes number in tree
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
/**
* Definition for Node.
* public class Node {
* int val;
* Node left;
* Node right;
* Node random;
* Node() {}
* Node(int val) { this.val = val; }
* Node(int val, Node left, Node right, Node random) {
* this.val = val;
* this.left = left;
* this.right = right;
* this.random = random;
* }
* }
*/
class Solution {
public NodeCopy copyRandomBinaryTree(Node root) {
Map<Node, NodeCopy> map = new HashMap<>();
return copy(root, map);
}
private NodeCopy copy(Node root, Map<Node, NodeCopy> map) {
if (root == null) return null;
NodeCopy newRoot = map.get(root);
if (newRoot == null) {
newRoot = new NodeCopy(root.val);
map.put(root, newRoot);
}
if (root.random != null) {
NodeCopy rand = map.get(root.random);
if (rand == null) {
rand = new NodeCopy(root.random.val);
map.put(root.random, rand);
}
newRoot.random = rand;
}
newRoot.left = copy(root.left, map);
newRoot.right = copy(root.right, map);
return newRoot;
}
static class NodeCopy {
int val;
NodeCopy left;
NodeCopy right;
NodeCopy random;
NodeCopy() {
}
NodeCopy(int val) {
this.val = val;
}
NodeCopy(int val, NodeCopy left, NodeCopy right, NodeCopy random) {
this.val = val;
this.left = left;
this.right = right;
this.random = random;
}
}
}
BFS
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
class Solution {
public NodeCopy copyRandomBinaryTree(Node root) {
if (root == null) {
return null;
}
Map<Node, NodeCopy> map = new HashMap<>();
map.put(root, new NodeCopy(root.val));
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
NodeCopy newNode = map.get(node);
if (node.random != null) {
if (!map.containsKey(node.random)) {
map.put(node.random, new NodeCopy(node.random.val));
}
newNode.random = map.get(node.random);
}
if (node.left != null) {
if (!map.containsKey(node.left)) {
map.put(node.left, new NodeCopy(node.left.val));
}
newNode.left = map.get(node.left);
queue.add(node.left);
}
if (node.right != null) {
if (!map.containsKey(node.right)) {
map.put(node.right, new NodeCopy(node.right.val));
}
newNode.right = map.get(node.right);
queue.add(node.right);
}
}
return map.get(root);
}
}