DEV Community


Posted on • Originally published at on

LeetCode: Clone Binary Tree With Random Pointer


Deep copy

Deep copy is a process in which the copying process occurs recursively. We need to clone all the elements of a tree.


The overall algorithm is recursive, but we need to find the previous cloned elements. So use a hashmap will help us to store the pair relationship of the elements of source tree and the new cloned elements.

class Solution {
    map<Node*, NodeCopy*> node_map;

    NodeCopy* copyRandomBinaryTree(Node* root) {
        if(root == NULL) return NULL;
        return dfs(root);

    NodeCopy* dfs(Node* cur) {
        if(cur == NULL) return NULL;
            return node_map[cur];
        NodeCopy* node = new NodeCopy(cur->val);
        node_map[cur] = node;
        node->left = dfs(cur->left);
        node->right = dfs(cur->right);
        node->random = dfs(cur->random);
        return node;

Enter fullscreen mode Exit fullscreen mode

The post LeetCode: Clone Binary Tree With Random Pointer appeared first on Coder's Cat.

Discussion (0)