Skip to content

1485. Clone Binary Tree With Random Pointer 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  NodeCopy* copyRandomBinaryTree(Node* root) {
    if (root == nullptr)
      return nullptr;
    if (const auto it = map.find(root); it != map.cend())
      return it->second;

    NodeCopy* newNode = new NodeCopy(root->val);
    map[root] = newNode;

    newNode->left = copyRandomBinaryTree(root->left);
    newNode->right = copyRandomBinaryTree(root->right);
    newNode->random = copyRandomBinaryTree(root->random);
    return newNode;
  }

 private:
  unordered_map<Node*, NodeCopy*> map;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public NodeCopy copyRandomBinaryTree(Node root) {
    if (root == null)
      return null;
    if (map.containsKey(root))
      return map.get(root);

    NodeCopy newNode = new NodeCopy(root.val);
    map.put(root, newNode);

    newNode.left = copyRandomBinaryTree(root.left);
    newNode.right = copyRandomBinaryTree(root.right);
    newNode.random = copyRandomBinaryTree(root.random);
    return newNode;
  }

  private Map<Node, NodeCopy> map = new HashMap<>();
}