차례
문제 정책
당신은 완전한 이진 트리 임의의 포인터로. 랜덤 포인터는 모든 노드가 왼쪽 및 오른쪽 자식이 아닌 다른 노드를 가리키는 노드를 참조합니다. 따라서 이것은 또한 간단한 이진 트리에서 노드의 표준 구조를 변경합니다. 이제 이진 트리의 노드는 현재 노드에 데이터를 저장하고 왼쪽, 오른쪽 및 임의 포인터에 대한 포인터를 저장합니다. 그래서 이제 우리는 문제가 무엇을 요구 하는가? "임의 포인터로 이진 트리 복제"문제는 주어진 초기 트리의 정확한 복사 본인 새 이진 트리를 만들도록 요청합니다. 따라서 새로 생성 된 트리에서 노드를 선택하면 왼쪽, 오른쪽 및 임의의 포인터가 원래 트리의 노드에 해당하는이 새 트리의 노드를 참조합니다.
예
입력
Inorder traversal of original binary tree is [current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5], Inorder traversal of cloned binary tree is[current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5],
설명
바이너리 트리의 왼쪽과 오른쪽 노드는 각 노드의 왼쪽과 오른쪽에 평소와 같이 표시됩니다. 그리고 다른 모든 포인터는 왼쪽 및 오른쪽 포인터가 임의의 포인터입니다. 일부 모서리에는 양방향 화살표가 있습니다. 노드의 부모에 대한 방향은 노드에 부모에 대한 임의의 포인터가 있음을 나타냅니다. 출력은 [현재 노드 데이터 / 임의 노드 데이터] 형식으로 제공됩니다.
해싱 접근법
따라서 우리는 초기 트리의 정확한 복사 본인 새 트리를 만들어야한다는 것을 알고 있습니다. inorder traversal을 실행하고 복사본을 만들 수 있습니다. 그러나 일부 노드가 아직 구성되지 않은 노드를 가리킬 수 있기 때문에 무작위 포인터 문제에 직면하게됩니다. 따라서이 오류를 제거합니다. 먼저 새 트리를 구성합니다. 그런 다음 해시맵 원래 트리의 각 노드에 해당하는 새 노드의 주소를 저장합니다. 따라서 다시 한 번 inorder traversal을 실행하고 HashMap에 값으로 저장되는 새 트리의 노드에 대한 임의의 포인터를 만듭니다.
효율적인 접근
위의 접근 방식에서 우리는 해시맵 원래 트리의 각 노드에 해당하는 복제 노드 주소를 저장했습니다. 그래서 그렇게하는 대신, 우리는 연결 목록 임의의 포인터로. 새로 생성 된 노드를 왼쪽 자식과 원래 트리의 해당 노드 사이에 밀어 넣습니다. 그래서 지금까지 초기 트리의 구조를 변경했습니다. 임의의 포인터를 설정하려면 노드에 해당하는 새 노드가 항상 왼쪽 자식이라는 것을 알고 있습니다. 따라서 입력 트리에서 노드의 왼쪽 자식에 무작위 포인터를 설정하기 만하면됩니다. 그러나 여전히 우리는 돌봐야 할 것이 하나 있습니다. 초기 및 복제 트리 노드의 왼쪽 자식을 복원해야합니다. 이 작업이 완료되면 무작위 포인터로 이진 트리를 복제했습니다.
암호
임의 포인터로 이진 트리를 복제하는 C ++ 코드
#include <iostream>
using namespace std;
struct node{
int data;
node *left, *right, *random;
};
node* create(int data){
node* tmp = new node();
tmp->data = data;
tmp->left = tmp->right = tmp->random = NULL;
}
// print inorder traversal of the given tree in [node, random node] format
void inorder(node* root)
{
if(root == NULL)
return;
// print inorder traversal of left tree
inorder(root->left);
// print in [current node, random node] format
cout << "[" << root->data << " ";
if (root->random == NULL)
cout << "NULL], ";
else
cout << root->random->data << "], ";
// print inorder traversal of right tree
inorder(root->right);
}
// insert clone nodes between the original node and its left child
node* insertCloneNode(node* originalNode)
{
if (originalNode == NULL)
return NULL;
node* left = originalNode->left;
originalNode->left = create(originalNode->data);
originalNode->left->left = left;
if(left != NULL)
left->left = insertCloneNode(left);
originalNode->left->right = insertCloneNode(originalNode->right);
return originalNode->left;
}
// sets the random pointers in clone tree
void setRandomNode(node* originalNode, node* cloneNode)
{
if (originalNode == NULL)
return;
if(originalNode->random != NULL)
cloneNode->random = originalNode->random->left;
else
cloneNode->random = NULL;
if(originalNode->left != NULL && cloneNode->left != NULL)
setRandomNode(originalNode->left->left, cloneNode->left->left);
setRandomNode(originalNode->right, cloneNode->right);
}
// after all the work restore the left pointers in original and clone tree
void restoreTreeLeftNode(node* originalNode, node* cloneNode)
{
if (originalNode == NULL)
return;
if (cloneNode->left != NULL)
{
node* cloneLeft = cloneNode->left->left;
originalNode->left = originalNode->left->left;
cloneNode->left = cloneLeft;
}
else
originalNode->left = NULL;
restoreTreeLeftNode(originalNode->left, cloneNode->left);
restoreTreeLeftNode(originalNode->right, cloneNode->right);
}
// constructs the new clone tree
node* cloneTree(node* originalNode)
{
if (originalNode == NULL)
return NULL;
node* cloneNode = insertCloneNode(originalNode);
setRandomNode(originalNode, cloneNode);
restoreTreeLeftNode(originalNode, cloneNode);
return cloneNode;
}
int main()
{
node *root = create(3);
node* two = create(2);
node* one = create(1);
node* seven = create(7);
node* five = create(5);
node* nine = create(9);
root->left = two;
root->left->left = one;
root->right = seven;
root->right->left = five;
root->right ->right = nine;
root->random = nine;
root->left->random = seven;
root->left->left->random = two;
root->right->random = one;
root->right->left->random = one;
root->right->right->random = five;
cout << "Inorder traversal of original binary tree is [current node data, random pointer data]: \n";
inorder(root);
node *clone = cloneTree(root);
cout << "\n\nInorder traversal of cloned binary tree is[current node data, random pointer data]: \n";
inorder(clone);
return 0;
}
Inorder traversal of original binary tree is [current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5], Inorder traversal of cloned binary tree is[current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5],
임의 포인터로 이진 트리를 복제하는 Java 코드
import java.util.*;
// Class that denotes a node of the tree
class node
{
int data;
node left, right, random;
public node(int data)
{
this.data = data;
left = right = random = null;
}
}
class Tree
{
static node root;
static node create(int data) {
node tmp = new node(data);
return tmp;
}
// print inorder traversal of the given tree in [node, random node] format
static void inorder(node root){
if(root != null){
// print inorder traversal of left tree
inorder(root.left);
// print in [current node, random node] format
System.out.print("[" + root.data + " ");
if(root.random == null)
System.out.print("null], ");
else
System.out.print(root.random.data +"], ");
// print inorder traversal of right tree
inorder(root.right);
}
}
// insert clone nodes between the original node and its left child
static node insertCloneNode(node originalNode)
{
if (originalNode == null)
return null;
node left = originalNode.left;
originalNode.left = create(originalNode.data);
originalNode.left.left = left;
if(left != null)
left.left = insertCloneNode(left);
originalNode.left.right = insertCloneNode(originalNode.right);
return originalNode.left;
}
// sets the random pointers in clone tree
static void setRandomNode(node originalNode, node cloneNode)
{
if (originalNode != null){
if(originalNode.random != null)
cloneNode.random = originalNode.random.left;
else
cloneNode.random = null;
if(originalNode.left != null && cloneNode.left != null)
setRandomNode(originalNode.left.left, cloneNode.left.left);
setRandomNode(originalNode.right, cloneNode.right);
}
}
// after all the work restore the left pointers in original and clone tree
static void restoreTreeLeftNode(node originalNode, node cloneNode)
{
if (originalNode != null) {
if (cloneNode.left != null)
{
node cloneLeft = cloneNode.left.left;
originalNode.left = originalNode.left.left;
cloneNode.left = cloneLeft;
}
else
originalNode.left = null;
restoreTreeLeftNode(originalNode.left, cloneNode.left);
restoreTreeLeftNode(originalNode.right, cloneNode.right);
}
}
// constructs the new clone tree
static node cloneTree(node originalNode)
{
if (originalNode == null)
return null;
node cloneNode = insertCloneNode(originalNode);
setRandomNode(originalNode, cloneNode);
restoreTreeLeftNode(originalNode, cloneNode);
return cloneNode;
}
public static void main(String[] args) {
node root = create(3);
node two = create(2);
node one = create(1);
node seven = create(7);
node five = create(5);
node nine = create(9);
root.left = two;
root.left.left = one;
root.right = seven;
root.right.left = five;
root.right .right = nine;
root.random = nine;
root.left.random = seven;
root.left.left.random = two;
root.right.random = one;
root.right.left.random = one;
root.right.right.random = five;
System.out.print("Inorder traversal of original binary tree is[current node data, random pointer data]: \n");
inorder(root);
node clone = cloneTree(root);
System.out.print("\n\nInorder traversal of cloned binary tree is[current node data, random pointer data]: \n");
inorder(clone);
}
}
Inorder traversal of original binary tree is[current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5], Inorder traversal of cloned binary tree is[current node data, random pointer data]: [1 2], [2 7], [3 9], [5 1], [7 1], [9 5],
랜덤 포인터로 이진 트리를 복제하기위한 복잡성 분석
시간 복잡성
의 위에), 우리는 이진 트리의 노드를 탐색했으며 이진 트리에는 N 개의 노드가 있기 때문입니다. 따라서 시간 복잡도는 선형입니다.
공간 복잡성
O (1), 배열이나지도에 정보를 저장하지 않았기 때문입니다. 따라서 공간 복잡성은 일정합니다.
