题目(LeetCode #1485)
给你一个二叉树，树中每个节点都含有一个附加的随机指针，该指针可以指向树中的任何节点或者指向空（null）。
请返回该树的 深拷贝 。
该树的输入/输出形式与普通二叉树相同，每个节点都用 [val, random_index] 表示：
val：表示 Node.val 的整数random_index：随机指针指向的节点（在输入的树数组中）的下标；如果未指向任何节点，则为 null 。
该树以 Node 类的形式给出，而你需要以 NodeCopy 类的形式返回克隆得到的树。NodeCopy 类和 Node 类定义一致。
示例1：
输入：root = [[1,null],null,[4,3],[7,0]]
输出：[[1,null],null,[4,3],[7,0]]
解释：初始二叉树为 [1,null,4,7] 。
节点 1 的随机指针指向 null，所以表示为 [1, null] 。
节点 4 的随机指针指向 7，所以表示为 [4, 3] 其中 3 是树数组中节点 7 对应的下标。
节点 7 的随机指针指向 1，所以表示为 [7, 0] 其中 0 是树数组中节点 1 对应的下标。
示例2：
输入：root = [[1,4],null,[1,0],null,[1,5],[1,5]]
输出：[[1,4],null,[1,0],null,[1,5],[1,5]]
解释：节点的随机指针可以指向它自身。
示例3：
输入：root = [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]
输出：[[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]
提示：
tree 中节点数目范围是 [0, 1000]- 每个节点的值的范围是
[1, 10^6]
题解
本题与 复制带随机指针的链表 类似，可先根据左右子树通过 DFS 复制树结构，同时使用 Map 保存原节点和克隆节点的关系，再遍历 Map 创建 random 指针即可。
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
| class Solution {
private Map<Node, NodeCopy> nodeMap;
public NodeCopy copyRandomBinaryTree(Node root) {
nodeMap = new HashMap<>();
NodeCopy rootCopy = dfs(root);
for (Map.Entry<Node, NodeCopy> entry : nodeMap.entrySet()) {
Node node = entry.getKey();
NodeCopy nodeCopy = entry.getValue();
nodeCopy.random = nodeMap.get(node.random);
}
return rootCopy;
}
private NodeCopy dfs(Node root) {
if (root == null) return null;
if (nodeMap.containsKey(root)) return nodeMap.get(root);
NodeCopy rootCopy = new NodeCopy(root.val);
rootCopy.left = dfs(root.left);
rootCopy.right = dfs(root.right);
nodeMap.put(root, rootCopy);
return rootCopy;
}
}
|
也可直接通过 DFS 递归地复制 random 指针，通过 Map 保存已经复制过的节点，避免栈溢出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
private Map<Node, NodeCopy> nodeMap;
public NodeCopy copyRandomBinaryTree(Node root) {
nodeMap = new HashMap<>();
return dfs(root);
}
private NodeCopy dfs(Node root) {
if (root == null) return null;
if (nodeMap.containsKey(root)) return nodeMap.get(root);
NodeCopy rootCopy = new NodeCopy(root.val);
nodeMap.put(root, rootCopy);
rootCopy.left = dfs(root.left);
rootCopy.right = dfs(root.right);
rootCopy.random = dfs(root.random);
return rootCopy;
}
}
|
可简化为如下形式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
private Map<Node, NodeCopy> nodeMap = new HashMap<>();
public NodeCopy copyRandomBinaryTree(Node root) {
if (root == null) return null;
if (nodeMap.containsKey(root)) return nodeMap.get(root);
NodeCopy rootCopy = new NodeCopy(root.val);
nodeMap.put(root, rootCopy);
rootCopy.left = copyRandomBinaryTree(root.left);
rootCopy.right = copyRandomBinaryTree(root.right);
rootCopy.random = copyRandomBinaryTree(root.random);
return rootCopy;
}
}
|