LeetCode 1485: Clone Binary Tree With Random Pointer

Explanation

To clone a binary tree with a random pointer, we can use a HashMap to map nodes in the original tree to their corresponding nodes in the cloned tree. We will perform a depth-first traversal of the original tree, creating new nodes in the cloned tree and mapping the original nodes to their clones in the HashMap. During this traversal, we will also set the random pointers of the cloned nodes based on the mapping in the HashMap.

Algorithmic Steps:

1. Perform a depth-first traversal of the original tree.
2. For each node encountered:
   • Create a new node in the cloned tree.
   • Map the original node to the cloned node in the HashMap.
   • Recursively clone the left and right children.
   • Set the random pointer of the cloned node based on the mapping in the HashMap.
3. Return the root of the cloned tree.

Time Complexity:

The time complexity of this approach is O(N), where N is the number of nodes in the binary tree. We visit each node exactly once during the traversal.

Space Complexity:

The space complexity of this approach is O(N), where N is the number of nodes in the binary tree. This space is used for the HashMap to store mappings between original and cloned nodes.

class Solution {
    private Map<Node, Node> map = new HashMap<>();

    public Node copyRandomBinaryTree(Node root) {
        if (root == null) {
            return null;
        }

        if (map.containsKey(root)) {
            return map.get(root);
        }

        Node clone = new Node(root.val);
        map.put(root, clone);
        clone.left = copyRandomBinaryTree(root.left);
        clone.right = copyRandomBinaryTree(root.right);
        clone.random = copyRandomBinaryTree(root.random);

        return clone;
    }
}