LeetCode 1485. 克隆含随机指针的二叉树
题目描述
题意分析
复制一棵二叉树，每个原节点除了值和左右孩子，还有一个
random指针，可以指向树中的任意节点或为空。结果中要为每个原节点创建独立的新节点，并保留三种指针之间的对应关系。这是深拷贝：新节点的
left、right、random都只能指向新树节点，不能继续引用原树。不同节点的值可能相同，仍需要各自的副本；多个原指针指向同一节点时，新指针也要共享同一个副本。随机指针可以形成自环或相互指向，不要求顺着树的父子方向。
解法：两趟 DFS + 身份映射
核心思路
[!blue]
如果创建节点时就尝试连接随机目标，目标副本可能尚未创建。把工作分成两遍：第一遍只创建全部新节点并建立对应关系，第二遍再统一连接指针，就能完全消除创建顺序的影响。
用映射
copies保存原节点对象到副本节点对象的对应。第一遍沿原树的left、right做迭代 DFS，为每个节点创建只含值的NodeCopy。树的左右孩子结构本身没有环，每个节点只有一个父节点，因此沿这两种边就能把全部节点创建一次，不需要沿random寻找节点。映射的键必须表达节点身份，而不是数值。Java 使用
IdentityHashMap明确按对象身份区分，Go 使用节点指针作为键。这样同值节点不会被合并，每个原对象始终对应唯一副本。第一遍结束后，所有非空随机目标都已经在映射里。第二遍再次沿左右孩子遍历，对每个原节点取出其副本，把三种指针分别设为原目标在映射中的副本。空目标查不到条目，自然得到空指针。
随机关系此时只需要一次查表，不触发新的遍历。自环会查到副本自身，多个来源指向同一目标会查到同一个副本，相互随机指向也都能同时保留。每条新引用都经由映射取得，因此不会残留原树引用，原树本身也不被修改。
两遍使用显式栈完成 DFS，第一遍栈耗尽后重新压入原根即可开始第二遍。最后返回原根在映射中的副本，空树在入口直接返回空。
解题步骤
- 原根为空时直接返回空，非空时创建节点身份映射和遍历栈。
- 先创建根的副本，再沿左右孩子遍历，为全部原节点建立对应的新节点。
- 第一遍结束后，再次把原根放入栈，开始第二次遍历。
- 对当前原节点查出副本，再分别用映射设置副本的左孩子、右孩子和随机指针。
- 继续沿原树左右孩子推进，不沿随机指针递归。
- 返回原根对应的新根。
代码实现
class Solution {
public NodeCopy copyRandomBinaryTree(Node root) {
if (root == null) {
return null;
}
// 按原节点身份创建副本，相同值的不同节点不能合并。
Map<Node, NodeCopy> copies = new IdentityHashMap<>();
Deque<Node> stack = new ArrayDeque<>();
copies.put(root, new NodeCopy(root.val));
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
if (node.left != null) {
copies.put(node.left, new NodeCopy(node.left.val));
stack.push(node.left);
}
if (node.right != null) {
copies.put(node.right, new NodeCopy(node.right.val));
stack.push(node.right);
}
}
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
NodeCopy copy = copies.get(node);
// 全部副本已创建，统一映射三个指针；空目标自然对应空指针。
copy.left = copies.get(node.left);
copy.right = copies.get(node.right);
// 只连接副本，不沿随机指针继续遍历；自环也指向副本自身。
copy.random = copies.get(node.random);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
return copies.get(root);
}
}
func copyRandomBinaryTree(root *Node) *NodeCopy {
if root == nil {
return nil
}
// 按原节点身份创建副本，相同值的不同节点不能合并。
copies := map[*Node]*NodeCopy{
root: {Val: root.Val},
}
stack := []*Node{
root,
}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if node.Left != nil {
copies[node.Left] = &NodeCopy{Val: node.Left.Val}
stack = append(stack, node.Left)
}
if node.Right != nil {
copies[node.Right] = &NodeCopy{Val: node.Right.Val}
stack = append(stack, node.Right)
}
}
stack = append(stack, root)
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
copy := copies[node]
// 全部副本已创建，统一映射三个指针；空目标自然对应空指针。
copy.Left = copies[node.Left]
copy.Right = copies[node.Right]
// 只连接副本，不沿随机指针继续遍历；自环也指向副本自身。
copy.Random = copies[node.Random]
if node.Left != nil {
stack = append(stack, node.Left)
}
if node.Right != nil {
stack = append(stack, node.Right)
}
}
return copies[root]
}
复杂度分析
- 时间复杂度：
O(n)。两遍各访问所有节点一次，每个节点创建一次并连接固定三个指针。- 空间复杂度：辅助空间
O(n)。映射保存全部对应关系，显式 DFS 栈至多为树高O(h)；返回的新树另占O(n)。
关键点总结
[!green]
- 左右孩子定义遍历范围，随机指针只定义需要复制的额外关系。
- 全部副本先创建，第二遍连接时任意合法目标都已经可以查到。
- 按对象身份建立一一对应，同时保留不同同值节点和共享目标。
- 所有新指针都指向映射得到的副本，自环与交叉随机引用无需特殊分支。
易错点总结
[!yellow]
- 按节点值作为映射键：不同同值节点会被合并，破坏树结构和随机关系。
- 直接把原随机指针赋给副本：结果仍然引用原树，不满足深拷贝。
- 第一遍就假定随机目标副本已存在：目标可能在尚未访问的其他分支，应该先建完全部节点。
- 沿随机指针无记录地继续搜索：随机引用可能成环，原左右孩子已经足以覆盖整棵树。
- 只复制值或只连接左右孩子：随机指针同样属于需要恢复的结构。
- 为每次随机引用另建目标节点：会把应当共享的目标拆成多份，必须复用统一映射。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 138. 随机链表的复制 | 中等 | 随机指针要求保存旧节点到新节点映射，才能保留共享引用，不能只复制值。 |
| 133. 克隆图 | 中等 | 加上随机边后也可视为图克隆，先登记副本再递归邻居以处理环或共享。 |