Կառուցեք Երկուական ծառ ՝ տրված arentնող զանգվածի ներկայացուցչությունից


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Microsoft Snapdeal
Դասավորություն Երկուական ծառ ծառ

«Կառուցեք երկուական ծառ ՝ տրված ծնողական զանգվածի ներկայացուցչությունից» խնդիրը նշում է, որ ձեզ կտրվի զանգված: Այս մուտքային զանգվածը ներկայացնում է երկուական ծառ: Այժմ դուք պետք է երկուական ծառ կառուցեք այս մուտքային զանգվածի հիման վրա: Rayանգվածը պահում է ծնողական հանգույցի ինդեքսը յուրաքանչյուր ինդեքսում:

Օրինակ

Կառուցեք Երկուական ծառ ՝ տրված arentնող զանգվածի ներկայացուցչությունից

Inorder Traversal: 3 1 0 4 2 5

Մոտեցում

Խնդիրը մեզ խնդրում է տրված ծնողից կառուցել երկուական ծառ դասավորություն ներկայացում Arնող զանգվածը պահում է մայր հանգույցի ինդեքսը զանգվածի յուրաքանչյուր ցուցիչում: Այժմ դուք պետք է երկուական ծառ կառուցեք ՝ օգտագործելով այս զանգվածը: Մուտքային զանգվածում -1 արժեքը նշանակում է արմատային հանգույցը ծառ.

Միամիտ մոտեցում է `շարունակել ստեղծել նոր հանգույցներ: Երբ մենք ստեղծում ենք այս հանգույցները, մենք միշտ ստեղծում ենք հանգույցները երկուական ծառի իրենց մակարդակի հերթականությամբ: Օրինակ, նախ, մենք ստեղծում ենք արմատ, այնուհետև դրա երեխաները և այլն: այն ժամանակ, երբ մենք ստեղծում ենք հանգույցները, ցուցիչների փոփոխության միջոցով մենք կապում ենք ծառի հանգույցները: Բայց այս մոտեցումը արդյունավետ չէ, քանի որ մենք ծառը կտրելու ենք ՝ գտնելու ներկայումս ստեղծված հանգույցի ծնողին:

Ավելի լավ և արդյունավետ լուծում է հետևել արդեն ստեղծված հանգույցներին: Այս կերպ մենք պետք չէ որոնել ընթացիկ հանգույցի ծնողը: Այս լուծումը մի փոքր այլ է: Այստեղ մենք նախ ստուգելու ենք, թե արդյոք մայր հանգույցը ստեղծվել է: Եթե ​​այն ստեղծվել է, ապա լավ է: Հակառակ դեպքում, մենք ռեկուրսիվ կերպով ստեղծում ենք բոլոր ծնողական հանգույցները, ապա ստեղծում մանկական հանգույցը: Այս կերպ մենք նաև շարունակում ենք կցել երեխայի հանգույցները ցուցիչի փոփոխությամբ:

Կոդ

C ++ ծածկագիր ՝ Երկուական ծառ կառուցելու համար ՝ տրված arentնող զանգվածի ներկայացուցչությունից

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void inorder(node* root){
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

void createNode(int a[], int i, node* created[]){
    // if current node is root
    if(a[i] == -1){
        node* cur = new node();
        cur->data = i;
        created[i] = cur;
        return;
    }

    // if the parent node has not been created
    if(created[a[i]] == NULL)
        createNode(a, a[i], created);

    // create current node
    node* cur = new node();
    cur->data = i;
    // insert the node value in created array
    created[i] = cur;

    // if left child of parent is null
    // attach current node as its left child
    if(created[a[i]]->left == NULL)
        created[a[i]]->left = cur;
    // else attach it as right child
    else if(created[a[i]]->right == NULL)
        created[a[i]]->right = cur;
}

int main()
{
  int a[] = {-1, 0, 0, 1, 2, 2};
  int n = (sizeof a) / (sizeof a[0]);
  node* created[n];
  memset(created, NULL, sizeof created);
  node* root = NULL;
  for(int i=0;i<n;i++){
        // if node has not been created
        if(created[i] == NULL)
            createNode(a, i, created);
        // store the root node
        if(a[i] == -1)
            root = created[i];
  }
  // print the inorder traversal of the root
  inorder(root);
}
3 1 0 4 2 5

Javaնողների զանգվածի տրված ներկայացուցչությունից Java կոդ ՝ Binary Tree կառուցելու համար

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static void inorder(node root){
      if(root != null){
          inorder(root.left);
          System.out.print(root.data+" ");
          inorder(root.right);
      }
  }

  static void createNode(int a[], int i, node created[]){
      // if current node is root
      if(a[i] == -1){
          node cur = new node();
          cur.data = i;
          created[i] = cur;
          return;
      }

      // if the parent node has not been created
      if(created[a[i]] == null)
          createNode(a, a[i], created);

      // create current node
      node cur = new node();
      cur.data = i;
      // insert the node value in created array
      created[i] = cur;

      // if left child of parent is null
      // attach current node as its left child
      if(created[a[i]].left == null)
          created[a[i]].left = cur;
      // else attach it as right child
      else if(created[a[i]].right == null)
          created[a[i]].right = cur;
  }

  public static void main(String[] args)
  {
    int a[] = {-1, 0, 0, 1, 2, 2};
    int n = 6;
    node created[] = new node[n];
    node root = null;
    for(int i=0;i<n;i++){
          // if node has not been created
          if(created[i] == null)
              createNode(a, i, created);
          // store the root node
          if(a[i] == -1)
              root = created[i];
    }
    // print the inorder traversal of the root
    inorder(root);
  }
}
3 1 0 4 2 5

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ չնայած մենք օգտագործում ենք ռեկուրսիա: Եթե ​​հանգույցը ստեղծվում է, մենք այլևս երբեք չենք ստեղծում նույն հանգույցը: Այսպիսով, ժամկետը գծային է:

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք ստեղծեցինք հանգույցների զանգված ՝ ստուգելու համար, արդյոք հանգույցը ստեղծվել է, թե ոչ: Այսպիսով, տարածության բարդությունը նույնպես գծային է: