Practice/Meta/Leetcode 1485. Clone Binary Tree With Random Pointer

Leetcode 1485. Clone Binary Tree With Random Pointer

CodingOptional

Problem

You are given the root of a binary tree where each node contains:

• An integer value
• A left pointer to the left child (or null)
• A right pointer to the right child (or null)
• A random pointer that can point to any node in the tree (or null)

Your task is to create a deep copy of this tree. The cloned tree must be a completely independent copy where:

• Each cloned node has the same value as its corresponding original node
• The tree structure (left and right pointers) is preserved
• All random pointers in the cloned tree point to the corresponding cloned nodes (not the original nodes)

Return the root of the cloned tree.

Requirements

1. Create new node instances for all nodes in the tree (deep copy, not shallow)
2. Preserve the binary tree structure using left and right pointers
3. Correctly map random pointers so cloned nodes reference other cloned nodes
4. Handle edge cases like empty trees and null random pointers
5. Ensure the original tree is not modified

Constraints

• The number of nodes in the tree is in the range [0, 1000]
• Each node's value is between -10^6 and 10^6
• The random pointer can point to any node in the tree or be null
• No two nodes will have the same memory address (but values can be duplicated)
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(n) for the cloned tree and auxiliary data structures

Examples

Example 1:

Input: root = [1, null, null, null] Node 1 with random pointing to itself Output: Cloned tree with one node, random pointing to the cloned node itself Explanation: The single node is cloned and its random pointer correctly references the cloned node

Example 2:

Input: root = [1, 2, 3, null, null, null, null] Tree structure: 1 / \ 2 3 Random pointers: 1->3, 2->1, 3->null Output: Cloned tree with same structure Cloned node 1's random points to cloned node 3 Cloned node 2's random points to cloned node 1 Cloned node 3's random is null Explanation: All structural and random relationships are preserved in the clone

Example 3:

Input: root = null Output: null Explanation: An empty tree clones to an empty tree