competitive/cloneatree.cpp at main · krishna-mathuria/competitive · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution{
  public:

Node* copyLeftRightNode(Node* treeNode, unordered_map<Node *, Node *> &mymap)
{
    if (treeNode == NULL)
        return NULL;
    Node* cloneNode = new Node(treeNode->data);
    mymap[treeNode] = cloneNode;
    cloneNode->left  = copyLeftRightNode(treeNode->left, mymap);
    cloneNode->right = copyLeftRightNode(treeNode->right, mymap);
    return cloneNode;
}


void copyRandom(Node* treeNode,  Node* cloneNode, unordered_map<Node *, Node *> &mymap)
{
    if (cloneNode == NULL)
        return;
    cloneNode->random =  mymap[treeNode->random];
    copyRandom(treeNode->left, cloneNode->left, mymap);
    copyRandom(treeNode->right, cloneNode->right, mymap);
}

// This function makes the clone of given tree. It mainly uses
// copyLeftRightNode() and copyRandom()
Node* cloneTree(Node* tree)
{
    if (tree == NULL)
        return NULL;
    unordered_map<Node *, Node *> mymap;
    Node* newTree = copyLeftRightNode(tree, mymap);
    copyRandom(tree, newTree, mymap);
    return newTree;
}
};