Problem Statement
The problem provides a unique structure of a binary tree where each node not only has the typical value and pointers to child nodes but also an additional random pointer. This random pointer can either point to any other node within the tree or can be null, introducing a complex layer to the structure. The main objective is to create a deep copy of this binary tree. Each node in the tree is represented by a pair [val, random_index], where val represents the value of the node, and random_index is the tree-wide index of the node to which the random pointer points, or null if there is no target for the random pointer.
Your task is to use the given class Node for the original tree nodes and generate a copy of this tree in the NodeCopy class, ensuring that the deep copy accurately replicates both the regular and random linkages between nodes.
Examples
Example 1
Input:
root = [[1,null],null,[4,3],[7,0]]
Output:
[[1,null],null,[4,3],[7,0]]
Explanation:
The original binary tree is [1,null,4,7]. The random pointer of node one is null, so it is represented as [1, null]. The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree. The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.
Example 2
Input:
root = [[1,4],null,[1,0],null,[1,5],[1,5]]
Output:
[[1,4],null,[1,0],null,[1,5],[1,5]]
Explanation:
The random pointer of a node can be the node itself.
Example 3
Input:
root = [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]
Output:
[[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]
Constraints
- The number of nodes in the
treeis in the range[0, 1000]. 1 <= Node.val <= 106
Approach and Intuition
To tackle the deep copy of a binary tree with random pointers, consider the following steps:
Creating a Mapping from Original to Copy:
- Utilize a hashtable to map each node in the original tree to its corresponding node in the cloned tree. This provides a straightforward means to relate every node with its copy and helps in correctly assigning random pointers later.
Clone Nodes Recursively:
- Traverse the original tree via a pre-order traversal: visit each node, copy its value, and recurse on its left and right children. This results in making clones of all nodes without setting up their random pointers.
Setting the Random Pointers:
- During the traversal, for each node in the original tree, determine the target of its random pointer, if it exists. Use the hashtable to find this target's corresponding clone and set it as the random pointer target of the current node's clone.
Connect Left and Right Pointers:
- For every node visited, set the left and right pointers of its clone by using the mapping to find the respective clones of its children.
By using this approach, the cloned tree will be structured identically to the original tree with all random links appropriately set, utilizing recursive depth-first search traversal augmented with a mapping technique to handle random pointers. This effectively ensures that both the structural and random connections are replicated in the deep copy.
Solutions
- C++
- Java
- Python
class Solution {
unordered_map<Node*, NodeCopy*> mapping;
NodeCopy* cloneSubGraph(Node* root) {
if (!root) {
return NULL;
}
queue<Node*> queueNodes;
queueNodes.push(root);
mapping[root] = new NodeCopy(root->val);
while (!queueNodes.empty()) {
Node* currentNode = queueNodes.front();
queueNodes.pop();
NodeCopy* copiedNode = mapping[currentNode];
if (currentNode->left) {
if (mapping.find(currentNode->left) == mapping.end()) {
queueNodes.push(currentNode->left);
mapping[currentNode->left] = new NodeCopy(currentNode->left->val);
}
copiedNode->left = mapping[currentNode->left];
}
if (currentNode->right) {
if (mapping.find(currentNode->right) == mapping.end()) {
queueNodes.push(currentNode->right);
mapping[currentNode->right] = new NodeCopy(currentNode->right->val);
}
copiedNode->right = mapping[currentNode->right];
}
if (currentNode->random) {
if (mapping.find(currentNode->random) == mapping.end()) {
queueNodes.push(currentNode->random);
mapping[currentNode->random] = new NodeCopy(currentNode->random->val);
}
copiedNode->random = mapping[currentNode->random];
}
}
return mapping[root];
}
public:
NodeCopy* copyRandomBinaryTree(Node* root) {
NodeCopy* clonedRoot = cloneSubGraph(root);
return clonedRoot;
}
};
This solution focuses on the problem of cloning a binary tree where each node has a random pointer apart from the usual left and right pointers. The C++ implementation uses a Breadth-First Search (BFS) approach facilitated by a queue and a hash map to handle the cloning process.
Start by creating an unordered map, mapping, to keep track of original nodes and their corresponding cloned nodes. This map is critical as it ensures that each node is cloned exactly once and helps in updating the random pointers appropriately.
The function cloneSubGraph handles the cloning process:
- Check if the input node,
root, isnullptr. If yes, returnnullptrindicating the tree is empty. - Initiate the cloning with the root node. Create its clone and store it in the map.
- Use a queue to traverse the tree level by level. For each node processed:
- Clone the left child if not already cloned.
- Clone the right child if not already cloned.
- Clone the random pointer node if not already cloned.
- Update the corresponding pointers in the cloned node to point to the appropriate cloned children or random nodes.
The main function copyRandomBinaryTree sets up the initial conditions for cloning and calls cloneSubGraph to perform the actual work, returning the cloned tree's root node. This ensures a deep copy of the entire tree structure, including the random links, using efficient BFS traversal and hash mapping.
class Solution {
private HashMap<Node, NodeCopy> mapping = new HashMap<>();
private NodeCopy cloneTree(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
mapping.put(root, new NodeCopy(root.val));
while (!queue.isEmpty()) {
Node current = queue.poll();
NodeCopy copiedNode = mapping.get(current);
if (current.left != null) {
if (!mapping.containsKey(current.left)) {
queue.add(current.left);
mapping.put(current.left, new NodeCopy(current.left.val));
}
copiedNode.left = mapping.get(current.left);
}
if (current.right != null) {
if (!mapping.containsKey(current.right)) {
queue.add(current.right);
mapping.put(current.right, new NodeCopy(current.right.val));
}
copiedNode.right = mapping.get(current.right);
}
if (current.random != null) {
if (!mapping.containsKey(current.random)) {
queue.add(current.random);
mapping.put(current.random, new NodeCopy(current.random.val));
}
copiedNode.random = mapping.get(current.random);
}
}
return mapping.get(root);
}
public NodeCopy copyRandomBinaryTree(Node root) {
NodeCopy clonedRoot = cloneTree(root);
return clonedRoot;
}
}
This Java program implements a solution to clone a binary tree wherein each node has an additional pointer, namely random, which can point to any node in the tree or null. Here's a rundown of the functionality:
- Utilizes a
HashMap<Node, NodeCopy>calledmappingto keep track of original nodes and their respective clones. - Defines a
cloneTreemethod responsible for deep cloning the tree structure. - Uses a
Queue<Node>to perform a breadth-first traversal of the original tree. - During the traversal:
- If a node has not been cloned yet, it creates a new
NodeCopyand adds it to the mapping. - Establishes the
left,right, andrandompointers in the cloned nodes by accessing the mapping.
- If a node has not been cloned yet, it creates a new
- Returns the root of the cloned tree structure from the
copyRandomBinaryTreemethod.
This approach ensures that both the structural and random connections of the original binary tree are preserved in its clone, making use of both queue-based BFS for systematic node copying and hashing to avoid duplication and manage linking seamlessly. An efficient solution to tackle complex tree structures with additional pointer requirements.
class Solution:
def __init__(self):
# Mapping originals to their copies
self.mapping = {None: None}
def traverse(self, node: 'Optional[Node]') -> 'Optional[NodeCopy]':
if not node:
return None
queue_nodes = deque()
queue_nodes.append(node)
self.mapping[node] = NodeCopy(node.val)
while queue_nodes:
current = queue_nodes.popleft()
copy_node = self.mapping[current]
for neighb in [current.left, current.right, current.random]:
if neighb and neighb not in self.mapping:
queue_nodes.append(neighb)
self.mapping[neighb] = NodeCopy(neighb.val)
if neighb:
setattr(copy_node, neighb.__class__.__name__.lower(), self.mapping[neighb])
return self.mapping[node]
def cloneRandomBinaryTree(self, node: 'Optional[Node]') -> 'Optional[NodeCopy]':
return self.traverse(node)
The provided Python code defines a solution for cloning a binary tree where each node has a random pointer in addition to the usual left and right pointers. Understanding this code involves recognizing the use of a breadth-first search (BFS) approach to traverse and replicate the original tree nodes, while maintaining a map of original nodes to their copies.
- First, initialize a map
self.mappingwith a key-value pair ofNone: Noneto handle leaf nodes. - Implement the
traversefunction to construct a duplicate of the input tree:- Use a queue
queue_nodesto facilitate BFS, starting with the input node. - Ensure each node is copied exactly once by checking if it's already in
self.mapping. If not, create a newNodeCopyfor the unseen node. - Expand the BFS to the left, right, and random pointers of each node, carefully updating the relationships in the copied tree analogous to the original tree structure.
- Use a queue
- The
cloneRandomBinaryTreefunction serves as a public API that takes a root node of a binary tree and returns a cloned tree by invoking thetraversemethod.
Ensure you secure error handling for non-typical cases, such as an empty tree, to avoid unnecessary traversal. This code efficiently handles the complexity of cloning a binary tree with the additional random pointer, ensuring a robust solution to the problem.
No comments yet.