文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 原地算法
    • 2.2 哈希表

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);} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1484. 克隆含随机指针的二叉树（哈希/递归）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。