کلون هڪ ثنائي وڻ کي بي ترتيب وار اشارو سان


تڪليف جي سطح سخت
بار بار پڇڻ ۾ قبول ڪريو Amazon Cisco حقيقت جو جائزو فاتح گوگل Microsoft جي ناٽڪ Snapchat
هاش وڻن

مسئلي جو بيان

توھان کي مڪمل ڏنو ويندو آھي بائنري وڻ ڪجهه بي ترتيب واري اشارن سان. ريمنڊ پوائنٽرس کي نوڊس جو حوالو ڏنو ويو آهي جيڪي هر نوڊ پنهنجي کاٻي ۽ سا childي ٻار کان سواءِ ٻين ڏانهن اشارو ڪن ٿا. تنهن ڪري ، اهو پڻ سادي بائنري وڻ ۾ نوڊ جي معياري جوڙجڪ بدلائي ٿو. هاڻ بائنري وڻ جو جوڙ موجوده نوڊ تي ڊيٽا کي اسٽور ڪندو ۽ کاٻي کان سا ،ي ، صحيح ۽ بي ترتيب واري پوائنٽر. تنهن ڪري ، هاڻي اسان سان وڃڻ سٺو آهي ته مسئلو به ڇا پڇندو آهي؟ مسئلو ”ڪلونري وڻ جنهن کي بي ترتيب واري اشارو ڏيندڙن سان آهي“ ٺاهن ٿا پڇون ٿا نئين بائنري وڻ کي ٺاهڻ لاءِ جيڪا ڏنل ابتدائي وڻ جي صحيح ڪاپي آهي. تنهن ڪري نئين پيدا ٿيل وڻ ۾ ، جيڪڏهن اسان هڪ کاڊ کڻي ان جو کاٻي ، سا ،ي ۽ اڻ ترتيب وارو اشارو ڏيندڙ نئين وڻ ۾ موجود نوڊس کي ظاهر ڪري جيڪي اصل وڻ ۾ جوڙ لاءِ ويجها آهن.

مثال

پٽ

کلون هڪ ثنائي وڻ کي بي ترتيب وار اشارو سان

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ي نوڊس هر نوڊ جي کاٻي ۽ سا onي پاسي معمول وانگر ڏيکاريا ويندا آهن. ۽ ٻيا سڀئي اشارو ڏيندڙ کاٻي ۽ سا pointي طرف وارو اشارو آهن. ڪجھ ڪنڊن ۾ ٻہ تارا آھن (اھو ٻنھي طرف اشارو ڪري رھيو آھي)۔ نوڊ جي والدين جي ڪنهن طرف هدايت اهو ظاهر ڪري ٿو ته نوڊ والدين لاءِ بي ترتيب پوائنٽر آهي. ٻاھر [موجوده نوڊ جي ڊيٽا / بي ترتيب نوڊ جي ڊيٽا] فارميٽ ۾ ڏنل آهي.

ڇڪڻ جي طريقي

تنهن ڪري ، جيئن اسان thatاڻون ٿا ته اسان کي هڪ نئون وڻ ٺاهڻ جي ضرورت آهي جيڪا ابتدائي وڻ جي صحيح ڪاپي آهي. اسان هڪ انوڊر ٽرورسل هلائي سگهندا آهيون ۽ ڪاپي ٺاهي سگهنداسين. پر اسان بي ترتيبي اشارن سان مسئلن کي منهن ڏينداسين ڇو ته ڪجهه نوڊس نوڊس ڏانهن اشارو ڪري رهيا آهن جيڪي اڃا تائين ٺهيل نه آهن. سو هن غلطي کان نجات حاصل ڪرڻ. اسان پھريائين ھڪڙو نئون وڻ ٺاھينداسين. پوءِ هڪ استعمال ڪريو هش ميپ جيڪو اصلي وڻ ۾ هر نوڊ جي برابر نئين نوڊ جو پتو محفوظ ڪري ٿو. تنهنڪري هڪ ڀيرو ٻيهر اسان هڪ انوڊر ٽرورسال هلائيندا آهيون ۽ بي ترتيب واري اشارو نئين وڻ جي نوڊس ڏانهن (جيڪي هشميپ ۾ قدر طور محفوظ ٿيل آهن).

ايڏي موثر رستو

مٿي ڏنل طريقي ۾ ، اسان کي رکڻو هو هش ميپ جنهن اصلي وڻ ۾ هر نوڊ جي برابر ڪلون نوڊ جو پتو محفوظ ڪيو. تنھنڪري ھٿ ڪرڻ بدران ، اسين ڪجھ ڪري وينداسين جيئن ڪلون اي ڳن listيل لسٽ بي ترتيب اشارو سان. اسان اصلي وڻ ۾ کاٻي نن andڙي ۽ ملندڙ نوڊ جي وچ ۾ نئين ٺهيل نوڊ کي زور ڏيون ٿا. تنهنڪري هاڻي تائين ، اسان ابتدائي وڻ جي haveانچي کي تبديل ڪيو آهي. بي ترتيب پوائنٽرن کي جوڙڻ لاءِ اسان knowاڻون ٿا ته هڪ نوڊ سان ملندڙ هڪ نئون نوڊ هميشه هن جو کاٻي ٻار آهي. ان طرح اسان صرف داخل ٿيل وڻ ۾ نوڊ جي کاٻي ٻار کي بي ترتيب وارو ترتيب ڏيندڙ نشان لڳايو. پر اڃا به اسان کي هڪ ئي خيال رکڻ گهرجي. اسان کي شروعاتي ۽ کلون واري وڻ جي نوڊن جو کاٻي ٻار کي بحال ڪرڻ گهرجي. هڪ دفعو اهو ٿي چڪو آهي ، اسان هڪ بائنري وڻ بي ترتيب ڪيو آهي پوائنٽ پوائنٽرن سان.

ڪوڊ

بي + وڻ سان ڪلينٽي وڻن کي بي ترتيب وارن پوائنٽن سان ڪلون ڪرڻ لاءِ 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],

جاوا ڪوڊ بيئنڊي جي وڻ کي بي ترتيب واري پوائنٽرن سان کلون ڪرڻ لاءِ

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

بي ترتيب واري وڻ کي ڪلونٽي اشارو سان گڏ کلڻ جو پيچيدگي تجزيو

وقت جي پيچيدگي 

اي (اين) ، اسان صرف بائنري وڻ ۾ نوڊس جا آثار وڌا آهن ، ۽ جيئن ته بائنري وڻ ۾ نوڊس آهن. ان ڪري وقت جي پيچيدگي سڌي آهي.

خلائي پيچيدگي

اي (1) ، جئين اسان صف ۽ نقشي ۾ ڪا معلومات محفوظ نه ڪئي آهي اھڙيءَ طرح خلائي پيچيدگي مستقل آھي.