本文共 3564 字，大约阅读时间需要 11 分钟。

1. 题目

给你一个二叉树，树中每个节点都含有一个附加的随机指针，该指针可以指向树中的任何节点或者指向空（null）。

请返回该树的 深拷贝 。

该树的输入/输出形式与普通二叉树相同，每个节点都用 [val, random_index] 表示：

val：表示 Node.val 的整数

random_index：随机指针指向的节点（在输入的树数组中）的下标；如果未指向任何节点，则为 null 。 该树以 Node 类的形式给出，而你需要以 NodeCopy 类的形式返回克隆得到的树。

示例 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]]

示例 4：

输入：root = [] 输出：[]

示例 5：

输入：root = [[1,null],null,[2,null],null,[1,null]] 输出：[[1,null],null,[2,null],null,[1,null]]

提示：

tree 中节点数目范围是 [0, 1000] 每个节点的值的范围是 [1, 10^6]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/clone-binary-tree-with-random-pointer

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

2.1 原地算法

• 先copy整棵树
• 再链接random

/** * Definition for a binary tree node. * struct Node { *     int val; *     Node *left; *     Node *right; *     Node *random; *     Node() : val(0), left(nullptr), right(nullptr), random(nullptr) {} *     Node(int x) : val(x), left(nullptr), right(nullptr), random(nullptr) {} *     Node(int x, Node *left, Node *right, Node *random) : val(x), left(left), right(right), random(random) {} * }; */class Solution {
   public:    NodeCopy* copyRandomBinaryTree(Node* root) {
       	if(!root) return NULL;        NodeCopy* newroot = new NodeCopy(root->val);        build(root, newroot);        connect(root, newroot, root, newroot);        return newroot;    }    void build(Node* root, NodeCopy* newroot)    {
       	if(root->left)    	{
       		NodeCopy* l = new NodeCopy(root->left->val);    		newroot->left = l;    		build(root->left, l);    	}    	if(root->right)    	{
       		NodeCopy* r = new NodeCopy(root->right->val);    		newroot->right = r;    		build(root->right, r);    	}    }    void connect(Node* root, NodeCopy* newroot, Node* cur1,  NodeCopy* cur2)    {
       	if(!cur1) return;    	if(cur1->random)    		cur2->random = find(root, newroot, cur1->random);    	connect(root, newroot, cur1->left, cur2->left);    	connect(root, newroot, cur1->right, cur2->right);    }    NodeCopy* find(Node* root, NodeCopy* newroot, Node* rd)    {
       	if(!root) return NULL;    	if(root == rd) return newroot;    	auto l = find(root->left, newroot->left, rd);    	if(l) return l;    	auto r = find(root->right, newroot->right, rd);    	return r;    }};

2.2 哈希表

class Solution {
   	unordered_map
   
     m;public:    NodeCopy* copyRandomBinaryTree(Node* root) {
       	if(!root) return NULL;        NodeCopy* newroot = new NodeCopy(root->val);        m[root] = newroot;        build(root, newroot);        connect(root, newroot);        return newroot;    }    void build(Node* root, NodeCopy* newroot)    {
       	if(root->left)    	{
       		NodeCopy* l = new NodeCopy(root->left->val);    		newroot->left = l;    		m[root->left] = l;    		build(root->left, l);    	}    	if(root->right)    	{
       		NodeCopy* r = new NodeCopy(root->right->val);    		newroot->right = r;    		m[root->right] = r;    		build(root->right, r);    	}    }    void connect(Node* root, NodeCopy* newroot)    {
       	if(!root) return;    	if(root->random)    		newroot->random = m[root->random];    	connect(root->left, newroot->left);    	connect(root->right, newroot->right);    }};
   

---

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107570532 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！