랜덤 포인터가 있는 두 갈래 트리 클론 a Binary Tree with Random Pointers

두 갈래 나무의 노드는 다음과 같은 구조를 가지고 있다

struct node {  
    int key; 
    struct node *left,*right,*random;
} 

포인터 랜덤은 나무의 임의의 노드를 무작위로 가리키거나 NULL을 가리킬 수 있습니다.함수를 써서 이 나무를 복제하세요.
생각:
1. Create new nodes in cloned tree and insert each new node in original tree between the left pointer edge of corresponding node in the original tree (See the below image). i.e. if current node is A and it’s left child is B ( A — >> B ), then new cloned node with key A wil be created (say cA) and it will be put as A — >> cA — >> B (B can be a NULL or a non-NULL left child). Right child pointer will be set correctly i.e. if for current node A, right child is C in original tree (A — >> C) then corresponding cloned nodes cA and cC will like cA —->> cC
2. Set random pointer in cloned tree as per original tree i.e. if node A’s random pointer points to node B, then in cloned tree, cA will point to cB (cA and cB are new node in cloned tree corresponding to node A and B in original tree)
3. Restore left pointers correctly in both original and cloned tree 아래에 step1과 step3의 두 함수를 제시합니다. 이 두 함수의 input는 아이를 좌우하는 노드만 있지만 이 두 함수를 쉽게 확장할 수 있습니다.

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#include <string.h>
#include <set>


#include <stdio.h>
#include <stdlib.h>

#define INT_MIN -100
#define INT_MAX 100
 
struct Node{
    int key;   Node* left;  Node* right;
    Node(int k, Node* l, Node* r): key(k), left(l), right(r){};
};


void copyLeftRight(Node* root)
// step 1
{
	if(root)
	{
		copyLeftRight(root->left);
		copyLeftRight(root->right);
	
		Node* newRoot = new Node(root->key, NULL, NULL);
		newRoot->left = root->left;
		if(root->right) 
			newRoot->right = root->right->left;

		root->left = newRoot;
	}
}

void restoreTree(Node* root)
// step 3
{
	if(root)
	{
		Node*left = root->left;
		if(left)
		{
			root->left = left->left;
			if(root->left)
				left->left = root->left->left;
		}

		restoreTree(root->left);
		restoreTree(root->right);
	}
	
}

void printTree(Node* root)  
{  
    if(root==NULL)  
        return;  
  
    cout<<root->key<<" ";  
    printTree(root->left);     
    printTree(root->right);    
}  

int main()
{
    Node* n1 = new Node(1,NULL,NULL);    
    Node* n3 = new Node(3,NULL,NULL);    
    Node* n2 = new Node(2,n1,n3);    
    Node* n5 = new Node(5,NULL,NULL);    
    Node* n4 = new Node(4,n2,n5);   
    Node* n0 = new Node(0, NULL, n4);
  /* Constructed binary tree is  
        0
         \
          4  
        /   \
       2     5  
      /  \
    1     3  */ 

	copyLeftRight(n0);
	Node* n0_copy = n0->left;

	restoreTree(n0);

	printTree(n0);
	cout<<endl;
	printTree(n0_copy);

}

완전한 해법은 다음과 같다.
http://www.geeksforgeeks.org/clone-binary-tree-random-pointers/