Clone ເປັນໄມ້ຢືນຕົ້ນຖານສອງມີຕົວຊີ້ທິດທາງແບບ Random


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Amazon Cisco ປັດໃຈ ສະ ເໜ່ ກູໂກ Microsoft Opera SnapChat
Hash ຕົ້ນໄມ້

ຖະແຫຼງການບັນຫາ

ເຈົ້າຍັງບໍ່ໄດ້ໃຫ້ຄົບຖ້ວນ ຕົ້ນໄມ້ຖານສອງ ກັບບາງຈຸດຊີ້ ນຳ. ຕົວຊີ້ວັດແບບບັງເອີນແມ່ນ ໝາຍ ເຖິງຂໍ້ທີ່ທຸກໆຂໍ້ໃຫ້ຂໍ້ຊີ້ໄປຫາບ່ອນອື່ນນອກ ເໜືອ ຈາກເດັກຊ້າຍແລະຂວາ. ສະນັ້ນ, ສິ່ງນີ້ກໍ່ປ່ຽນແປງໂຄງສ້າງມາດຕະຖານຂອງ node ໃນຕົ້ນໄມ້ຖານສອງ. ດຽວນີ້ node ຂອງຕົ້ນໄມ້ໄບນາລີຈະເກັບຂໍ້ມູນຢູ່ທີ່ node ປັດຈຸບັນແລະຕົວຊີ້ໄປທາງຊ້າຍ, ຂວາແລະ pointer ແບບສຸ່ມ. ສະນັ້ນ, ດຽວນີ້ພວກເຮົາດີທີ່ຈະໄປກ່ຽວຂ້ອງກັບບັນຫາຫຍັງທີ່ຍັງຖາມ? ບັນຫາ“ Clone ເປັນຕົ້ນໄມ້ຖານສອງທີ່ມີຈຸດຊີ້ ນຳ ແບບສຸ່ມ” ຂໍໃຫ້ສ້າງຕົ້ນໄມ້ໄບນາລີຄູ່ ໃໝ່ ເຊິ່ງເປັນ ສຳ ເນົາທີ່ແນ່ນອນຂອງຕົ້ນໄມ້ເບື້ອງຕົ້ນທີ່ໃຫ້. ສະນັ້ນໃນຕົ້ນໄມ້ທີ່ຖືກສ້າງຂື້ນ ໃໝ່, ຖ້າພວກເຮົາເລືອກເອົາ node ຂອງມັນຢູ່ເບື້ອງຊ້າຍ, ຂວາແລະ pointer ແບບສຸ່ມ ໝາຍ ເຖິງຂໍ້ໃນຕົ້ນໄມ້ ໃໝ່ ນີ້ທີ່ສອດຄ້ອງກັບຂໍ້ທີ່ຢູ່ໃນຕົ້ນໄມ້ຕົ້ນ.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ

Clone ເປັນໄມ້ຢືນຕົ້ນຖານສອງມີຕົວຊີ້ທິດທາງແບບ Random

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

ຄໍາອະທິບາຍ

ຂໍ້ເບື້ອງຊ້າຍແລະຂວາຂອງຕົ້ນໄມ້ໄບນາລີແມ່ນສະແດງຢູ່ໃນເບື້ອງຊ້າຍແລະຂວາຂອງແຕ່ລະຂໍ້. ແລະຜູ້ຊີ້ບອກທັງ ໝົດ ທີ່ຊີ້ໄປທາງຊ້າຍແລະຂວາແມ່ນຕົວຊີ້ບອກແບບສຸ່ມ. ບາງແຄມມີລູກສອນຄູ່ (ນັ້ນແມ່ນທິດທາງທັງສອງທິດທາງ). ທິດທາງຕໍ່ພໍ່ແມ່ໃດ ໜຶ່ງ ຂອງ node ໝາຍ ຄວາມວ່າ node ມີຕົວຊີ້ແບບສຸ່ມໄປຫາພໍ່ແມ່. ຜົນຜະລິດໄດ້ຖືກມອບໃຫ້ເປັນ [ຮູບແບບຂໍ້ມູນ node ໃນປະຈຸບັນ / ແບບສຸ່ມຂໍ້ມູນ node].

ວິທີການລົບກວນ

ສະນັ້ນ, ດັ່ງທີ່ພວກເຮົາຮູ້ແລ້ວວ່າພວກເຮົາຕ້ອງການສ້າງຕົ້ນໄມ້ ໃໝ່ ເຊິ່ງເປັນການເຮັດ ສຳ ເນົາຕົ້ນໄມ້ທີ່ແນ່ນອນ. ພວກເຮົາສາມາດ ດຳ ເນີນການເຄື່ອນໄຫວແບບບໍ່ມີຕົວຕົນແລະສ້າງ ສຳ ເນົາ. ແຕ່ພວກເຮົາຈະປະເຊີນກັບບັນຫາກັບຈຸດຊີ້ ນຳ ແບບສຸ່ມ, ເພາະວ່າບາງຂໍ້ຂໍ້ ກຳ ລັງອາດຈະຊີ້ໄປທີ່ຂໍ້ທີ່ບໍ່ໄດ້ສ້າງ. ສະນັ້ນເພື່ອ ກຳ ຈັດຄວາມຜິດພາດນີ້. ກ່ອນອື່ນ ໝົດ ພວກເຮົາຈະສ້າງຕົ້ນໄມ້ ໃໝ່. ຫຼັງຈາກນັ້ນ, ໃຊ້ a HashMap ເຊິ່ງເກັບຮັກສາທີ່ຢູ່ຂອງ node ໃໝ່ ທີ່ສອດຄ້ອງກັບແຕ່ລະ node ໃນຕົ້ນໄມ້ຕົ້ນ. ດັ່ງນັ້ນອີກເທື່ອ ໜຶ່ງ ພວກເຮົາ ດຳ ເນີນການປ່ຽນເສັ້ນທາງທີ່ບໍ່ມີຕົວຕົນແລະເຮັດໃຫ້ຈຸດຊີ້ ນຳ ແບບສຸ່ມກັບຂໍ້ຂອງຕົ້ນໄມ້ ໃໝ່ (ເຊິ່ງເກັບໄວ້ເປັນຄ່າໃນ HashMap).

ວິທີການທີ່ມີປະສິດຕິພາບ

ໃນວິທີການຂ້າງເທິງ, ພວກເຮົາຕ້ອງຮັກສາກ HashMap ເຊິ່ງເກັບຮັກສາທີ່ຢູ່ clone ທີ່ສອດຄ້ອງກັບແຕ່ລະ node ໃນຕົ້ນໄມ້ຕົ້ນ. ສະນັ້ນແທນທີ່ຈະເຮັດສິ່ງນັ້ນ, ພວກເຮົາຈະເຮັດບາງສິ່ງບາງຢ່າງທີ່ເຮັດເພື່ອກ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ ກັບຕົວຊີ້ວັດແບບສຸ່ມ. ພວກເຮົາຈະຍູ້ສາຍທີ່ສ້າງຂື້ນ ໃໝ່ ລະຫວ່າງເດັກນ້ອຍຊ້າຍແລະຂໍ້ທີ່ສອດຄ້ອງກັນຢູ່ໃນຕົ້ນໄມ້ຕົ້ນ. ສະນັ້ນຈົນເຖິງປະຈຸບັນ, ພວກເຮົາໄດ້ປ່ຽນໂຄງສ້າງຂອງຕົ້ນໄມ້ເບື້ອງຕົ້ນ. ເພື່ອ ກຳ ນົດຈຸດຊີ້ ນຳ ແບບສຸ່ມພວກເຮົາຮູ້ວ່າ Node ໃໝ່ ທີ່ສອດຄ້ອງກັບ Node ແມ່ນເດັກທີ່ຍັງເຫຼືອຢູ່. ດັ່ງນັ້ນພວກເຮົາພຽງແຕ່ຕັ້ງຕົວຊີ້ແບບສຸ່ມໄປຫາລູກເບື້ອງຊ້າຍຂອງຂໍ້ໃນຕົ້ນໄມ້ປ້ອນຂໍ້ມູນ. ແຕ່ພວກເຮົາຍັງມີສິ່ງ ໜຶ່ງ ທີ່ຄວນເບິ່ງແຍງ. ພວກເຮົາ ຈຳ ເປັນຕ້ອງຟື້ນຟູຂໍ້ມູນຂອງລູກທີ່ຢູ່ເບື້ອງຊ້າຍຂອງຕົ້ນໄມ້ຕົ້ນໄມ້ແລະໂຄນ. ເມື່ອໃດທີ່ໄດ້ເຮັດແລ້ວພວກເຮົາໄດ້ cloned ຕົ້ນໄມ້ຖານສອງທີ່ມີpoinṭersແບບສຸ່ມ.

ລະຫັດ

ລະຫັດ C ++ ເພື່ອ Clone Binary Tree ກັບ Random Pointers

#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 ເພື່ອ Clone Tree Binary ກັບ Random Pointers

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

ການວິເຄາະຄວາມສັບສົນເພື່ອ Clone ເປັນໄມ້ຢືນຕົ້ນຖານສອງກັບຕົວຊີ້ວັດ Random

ຄວາມສັບສົນເວລາ 

ໂອ (N), ພວກເຮົາຫາຂໍ້ມູນຢູ່ໃນຕົ້ນໄມ້ຖານສອງ, ແລະນັບຕັ້ງແຕ່ມີ N Nodes ໃນຕົ້ນໄມ້ຄູ່. ດັ່ງນັ້ນຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ດັ່ງທີ່ພວກເຮົາບໍ່ໄດ້ເກັບຂໍ້ມູນໃດໆໃນແຜນຜັງຫລືແຜນທີ່. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນຄົງທີ່.