LeetCode 1484. 克隆含随机指针的二叉树（哈希/递归）
LeetCode 1484. 克隆含随机指针的二叉树（哈希/递归）
文章目录
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. 解题
类似题目：LeetCode 138. 复制带随机指针的链表（哈希 / 深拷贝）
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<Node*,NodeCopy*> 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);
}
};腾讯云开发者
