forked from fishercoder1534/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
_1485.java
107 lines (91 loc) · 2.67 KB
/
_1485.java
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
package com.fishercoder.solutions;
import java.util.HashMap;
import java.util.Map;
public class _1485 {
public static class Solution1 {
public NodeCopy copyRandomBinaryTree(Node root) {
if (root == null) {
return null;
}
Map<Node, NodeCopy> map = new HashMap<>();
map.put(root, new NodeCopy(root.val));
dfs(root, map);
dfsConnect(root, map);
return map.get(root);
}
private void dfsConnect(Node root, Map<Node, NodeCopy> map) {
if (root == null) {
return;
}
NodeCopy copy = map.get(root);
if (root.left != null) {
copy.left = map.get(root.left);
}
if (root.right != null) {
copy.right = map.get(root.right);
}
if (root.random != null) {
copy.random = map.get(root.random);
}
map.put(root, copy);
dfsConnect(root.left, map);
dfsConnect(root.right, map);
}
private void dfs(Node root, Map<Node, NodeCopy> map) {
if (root == null) {
return;
}
NodeCopy copy = map.getOrDefault(root, new NodeCopy(root.val));
if (root.left != null) {
copy.left = new NodeCopy(root.left.val);
}
if (root.right != null) {
copy.right = new NodeCopy(root.right.val);
}
if (root.random != null) {
copy.random = new NodeCopy(root.random.val);
}
map.put(root, copy);
dfs(root.left, map);
dfs(root.right, map);
}
}
public static class Node {
int val;
public Node left;
public Node right;
public Node random;
public Node() {
}
;
public Node(int val) {
this.val = val;
}
;
public Node(int val, Node left, Node right, Node random) {
this.val = val;
this.left = left;
this.right = right;
this.random = random;
}
}
public static class NodeCopy {
int val;
public NodeCopy left;
public NodeCopy right;
public NodeCopy random;
public NodeCopy() {
}
;
public NodeCopy(int val) {
this.val = val;
}
;
public NodeCopy(int val, NodeCopy left, NodeCopy right, NodeCopy random) {
this.val = val;
this.left = left;
this.right = right;
this.random = random;
}
}
}