Leetcode Problem 1485. Clone Binary Tree With Random Pointer

1485. Clone Binary Tree With Random Pointer

Leetcode Solutions

Depth-First Search On Binary Tree ( Passes)

  1. Create a hash map newOldPairs to map original nodes to their copies.
  2. Define a recursive function deepCopy(root) that creates a copy of the tree without random pointers:
    • If root is NULL, return NULL.
    • Create a new node newRoot with the same value as root.
    • Recursively call deepCopy for root->left and root->right and attach them to newRoot.
    • Store the pair (root, newRoot) in newOldPairs.
    • Return newRoot.
  3. Define a recursive function mapRandomPointers(oldNode) to set the random pointers in the copied tree:
    • If oldNode is NULL, return.
    • Find the random node newRootRandom for newRoot using newOldPairs and set the random pointer.
    • Recursively call mapRandomPointers for oldNode->left and oldNode->right.
  4. Call deepCopy(root) to create the deep copy of the tree.
  5. Call mapRandomPointers(root) to set all random pointers.
  6. Return the new tree's root.
UML Thumbnail

Depth-First Search On Graph ( Pass)

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...