上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* Definition for a 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) {
}
};
cpp 解法, 执行用时: 208 ms, 内存消耗: 74.6 MB, 提交时间: 2023-10-16 21:58:42
/**
* 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:
unordered_map<Node *, NodeCopy *> seen;
NodeCopy* copyRandomBinaryTree(Node* root) {
return dfs(root);
}
NodeCopy * dfs(Node * rt) {
if (rt == NULL)
return NULL;
if (seen.find(rt) != seen.end())
return seen[rt];
NodeCopy * cur = new NodeCopy(rt->val);
seen[rt] = cur;
cur->left = dfs(rt->left);
cur->right = dfs(rt->right);
cur->random = dfs(rt->random);
return cur;
}
};
python3 解法, 执行用时: 200 ms, 内存消耗: 21.4 MB, 提交时间: 2023-10-16 21:57:42
# Definition for a binary tree node.
# class Node:
# def __init__(self, val=0, left=None, right=None, random=None):
# self.val = val
# self.left = left
# self.right = right
# self.random = random
class Solution:
def copyRandomBinaryTree(self, root: 'Node') -> 'NodeCopy':
seen = dict()
def dfs(root: 'Node') -> 'NodeCopy':
if root == None:
return None
if root in seen:
return seen[root]
cur = NodeCopy(root.val)
seen[root] = cur #早入seen。最后再入就溢出了
cur.left = dfs(root.left)
cur.right = dfs(root.right)
cur.random = dfs(root.random)
return cur
return dfs(root)
def copyRandomBinaryTree2(self, root: 'Node') -> 'NodeCopy':
if root == None:
return None
new_root = NodeCopy(root.val)
seen = dict()
seen[root] = new_root
Q = [root]
while Q:
x = Q.pop(0)
if x.left:
Q.append(x.left)
seen[x].left = seen[x.left] = NodeCopy(x.left.val) #指针的关系，不断链
if x.right:
Q.append(x.right)
seen[x].right = seen[x.right] = NodeCopy(x.right.val)
for n, ncopy in seen.items():
if n.random in seen.keys():
ncopy.random = seen[n.random]
return new_root
golang 解法, 执行用时: 80 ms, 内存消耗: 7.2 MB, 提交时间: 2023-10-16 21:57:01
/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Random *Node
* }
*/
func copyRandomBinaryTree(root *Node) *NodeCopy {
connects := map[*Node]*NodeCopy{}
var dfs func(root *Node)
dfs = func(root *Node) {
if root == nil {
return
}
nNode := &NodeCopy{Val:root.Val}
connects[root] = nNode
dfs(root.Left)
dfs(root.Right)
}
dfs(root)
for old, new := range connects {
new.Left = connects[old.Left]
new.Right = connects[old.Right]
new.Random = connects[old.Random]
}
return connects[root]
}
golang 解法, 执行用时: 80 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-16 21:56:43
/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Random *Node
* }
*/
func copyRandomBinaryTree(root *Node) *NodeCopy {
dic := map[*Node]*NodeCopy{}
var copyTree func(node *Node) *NodeCopy
copyTree = func(node *Node) *NodeCopy {
if node == nil {
return nil
}
if dic[node] == nil {
dic[node] = &NodeCopy{}
}
dic[node].Val = node.Val
if node.Random != nil {
if dic[node.Random] == nil {
dic[node.Random] = &NodeCopy{}
}
dic[node].Random = dic[node.Random]
}
dic[node].Left = copyTree(node.Left)
dic[node].Right = copyTree(node.Right)
return dic[node]
}
return copyTree(root)
}
