LeetCode 1485: Clone Binary Tree With Random Pointer Solution

Master LeetCode problem 1485 (Clone Binary Tree With Random Pointer), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1485. Clone Binary Tree With Random Pointer

Medium

Hash Table Tree Depth-First Search Breadth-First Search Binary Tree

Problem Explanation

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:

Perform a depth-first traversal of the original tree.
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.
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.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1485 (Clone Binary Tree With Random Pointer)?

This page provides optimized solutions for LeetCode problem 1485 (Clone Binary Tree With Random Pointer) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1485 (Clone Binary Tree With Random Pointer)?

The time complexity for LeetCode 1485 (Clone Binary Tree With Random Pointer) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1485 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1485 in Java, C++, or Python.

Back to LeetCode Solutions