LeetCode 1485. 克隆含随机指针的二叉树

2024-01-03 HGNULB 约 7 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1485. 克隆含随机指针的二叉树

题意分析

给一棵二叉树，每个节点除了 val、left、right，还多一个 random 指针，可以指向树中任意一个节点，也可以是空。要求返回这棵树的深拷贝：新树的结构、值、以及 random 的指向关系都与原树一致，但所有节点都必须是新建的对象，新树里不能出现任何指向原树节点的指针。

「深拷贝」这三个字是全题的判定标准。random 指向哪个节点，在新树里就必须指向对应的那个新节点——不是值相同的某个节点（值可能重复），也不是原树的那个节点（那就成了浅拷贝）。这意味着我们需要一个从「原节点」到「新节点」的身份级别的对应关系，而不是值级别的。

random 的存在把这个结构从「树」变成了「图」。普通二叉树拷贝之所以能一行递归搞定，是因为 left/right 子树互不相交、每个节点恰好被访问一次。加上 random 之后，同一个节点可能从多条路径被抵达：既可能作为某人的左孩子，又可能作为另一个人的 random 目标。于是两个问题立刻出现——重复创建（同一原节点被拷了两份，random 指向的和 left 指向的不是同一个对象）和指向尚未创建的节点（random 目标在遍历序中还在后面）。

约束里节点数到 $10^4$，值不超过 $10^4$ 且可能重复。值可重复这一条直接否掉了「用 val 当映射键」的做法。$10^4$ 的规模让 $O(n)$ 的哈希表方案毫无压力，但也意味着递归深度在极端链状树下可达 $10^4$，需要心里有数。

边界：空树返回空；random 为空要如实拷成空；random 指向自己（自环）；两个节点的 random 互相指向（互指环）；整棵树是一条长链。

解法：DFS + 哈希表映射原节点到克隆节点

核心思路

random 可能形成自环或互指，结构应按图来克隆。核心是维护身份映射 copies[original] = clone：同一个原节点始终对应同一个新对象，键必须是节点引用，不能是可能重复的 val。

节点数可达一万，递归 DFS 在退化树上依赖运行时栈大小。这里使用显式栈做两趟 DFS：第一趟只沿 left/right 遍历原二叉树，为每个节点创建唯一副本；第二趟再次遍历，把副本的 left/right/random 都指向映射中的对应副本。

第一趟的不变量是：已发现的每个原节点都恰有一个尚未连边的克隆。第二趟的不变量是：出栈节点的三个指针会被完整映射，此前处理过的克隆均已连边正确。

正确性说明：left/right 边能到达原树的全部节点，所以第一趟建立完整的一一映射。第二趟对每条原指针 u → v 写入 copy(u) → copy(v)；空指针仍为空，非空指针只指向新对象。于是值、树结构和所有随机关系均与原树一致，且没有任何引用泄漏到原树。

解题步骤

空树直接返回空。

创建根副本并登记映射，用显式栈沿左右孩子遍历，为每个原节点创建一次副本。

重新从根开始 DFS；对当前原节点，从映射中取出其副本。

将副本的 left、right、random 分别设为对应原指针在映射中的值。

第二趟结束后返回根对应的副本。

自环 node.random = node 会映射为 copy.random = copy；A、B 互相随机指向时，两条边也都落在 A、B 的副本之间。重复节点值不会冲突，因为映射按对象身份区分。

代码实现

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.Map;

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)$。两趟 DFS 都只访问每个树节点一次。

空间复杂度：$O(n)$。身份映射保存 n 个条目；显式栈最多为 $O(h)$，新树本身属于输出。

关键点总结

随机指针把树扩展成对象图，深拷贝必须维护“原对象到新对象”的身份映射。

先创建全部副本再统一连边，天然处理前向引用、自环和互指环。

第一趟只需沿左右孩子发现节点，因为题目保证 random 指向树内节点。

显式栈避免退化树造成递归栈溢出，仍保持 DFS 的线性复杂度。

易错点总结

用节点值作映射键：两个值同为 7 的不同节点会合并成一个副本，结构和随机指针都被破坏。

把 copy.random 直接赋成 node.random：新树会引用原树节点，属于浅拷贝。

第一趟尚未创建完就直接查随机目标：随机指针可能指向尚未访问的节点，映射查询会得到空。

第二趟漏连 random：左右结构虽正确，随机关系全部丢失。

每遇到一次引用就新建节点：同一目标会产生多个副本，自环还会无限创建。

递归遍历一万层退化树：Java 可能抛出 StackOverflowError；显式栈不依赖调用栈深度。

相似题目

题目	难度	考察点
133. 克隆图	中等	无向图任意成环，邻居是列表而非固定两个指针，映射表的作用完全一致
138. 随机链表的复制	中等	一维版本，可用「交织插入 + 拆分」做到 $O(1)$ 额外空间，是本题的经典对照
1490. 克隆 N 叉树	中等	无 `random` 因而无环，孩子数不定，纯递归即可，不需要映射表
297. 二叉树的序列化与反序列化	困难	通过字符串中转实现等价的深拷贝，重点在空节点的编码与解析的一致性
652. 寻找重复的子树	中等	同样用哈希表登记子树，但键是结构签名而非节点身份，考的是子树的相等判定
226. 翻转二叉树	简单	纯 `left`/`right` 的递归骨架，可用来对照理解「没有 random 时为何不需要表」