Клонирайте двоично дърво с произволни указатели  


Ниво на трудност Трудно
Често задавани в Аколит Амазонка Cisco FactSet Фанатиците Google Microsoft опера Snapchat
Хашиш Дърво

Декларация за проблема  

Дадено ви е пълно двоично дърво с някои случайни указатели. Случайните указатели се отнасят до възли, към които всеки възел сочи, различни от неговото ляво и дясно дете. Така че, това също променя стандартната структура на възел в обикновено двоично дърво. Сега възелът на двоично дърво ще съхранява данните в текущия възел и указател наляво, надясно и произволен указател. И така, сега е добре да продължим с това, което изобщо задава проблемът? Проблемът „Клониране на двоично дърво с произволни указатели“ изисква да се създаде ново двоично дърво, което е точно копие на даденото първоначално дърво. Така че в новото създадено дърво, ако изберем възел, неговият ляв, десен и произволен указател се отнася до възлите в това ново дърво, които съответстват на възлите в оригиналното дърво.

Пример  

Вход

Клонирайте двоично дърво с произволни указателищифт

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],

Обяснение

Левият и десният възел на двоичното дърво са показани както обикновено отляво и отдясно на всеки възел. И всички указатели, останалите ляв и десен указатели са произволни указатели. Някои ръбове имат двойни стрелки (което сочи в двете посоки). Посоката към който и да е от родителите на възела означава, че възелът има случаен указател към родител. Резултатът е даден във формат [текущи данни за възли / данни за произволни възли].

Вижте също
Възстановяване на двоично дърво за търсене

Хеширащ подход  

Тъй като знаем, че трябва да създадем ново дърво, което е точно копие на първоначалното дърво. Можем да изпълним вътрешно обръщане и да създадем копие. Но ще се сблъскаме с проблеми със случайни указатели, защото някои възли може да сочат към възли, които все още не са конструирани. Така че, за да се отървете от тази грешка. Първо ще конструираме ново дърво. След това използвайте a HashMap който съхранява адреса на новия възел, съответстващ на всеки възел в оригиналното дърво. Така че за пореден път стартираме обръщане в ред и правим произволни указатели към възлите на новото дърво (които се съхраняват като стойности в HashMap).

Ефективен подход  

В горния подход трябваше да запазим a HashMap който съхранява адрес на клониран възел, съответстващ на всеки възел в оригиналното дърво. Така че, вместо да правим това, ние ще направим нещо като направено за клониране на a свързан списък със случайни указатели. Ще избутаме новосъздадените възли между лявото дете и съответния възел в оригиналното дърво. Така че досега сме променили структурата на първоначалното дърво. За да зададем произволни указатели, знаем, че нов възел, съответстващ на възел, винаги е лявото му дете. По този начин ние просто задаваме произволния указател на лявото дъщерно устройство на възела в дървото за въвеждане. Но все пак трябва да се грижим за едно нещо. Трябва да възстановим лявото дъщерно устройство на възлите на първоначалното дърво и клониране. След като приключим, клонирахме двоично дърво със случайни указатели.

код  

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), тъй като не сме съхранили никаква информация в масив или карта. По този начин сложността на пространството е постоянна.