നൽകിയ രക്ഷാകർതൃ അറേ പ്രാതിനിധ്യത്തിൽ നിന്ന് ബൈനറി ട്രീ നിർമ്മിക്കുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ മൈക്രോസോഫ്റ്റ് സ്നാപ്ഡേൽ
അറേ ബൈനറി ട്രീ വൃക്ഷം

“തന്നിരിക്കുന്ന രക്ഷാകർതൃ അറേ പ്രാതിനിധ്യത്തിൽ നിന്ന് ബൈനറി ട്രീ നിർമ്മിക്കുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു ശ്രേണി നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. ഈ ഇൻപുട്ട് അറേ ഒരു ബൈനറി ട്രീയെ പ്രതിനിധീകരിക്കുന്നു. ഈ ഇൻപുട്ട് അറേയുടെ അടിസ്ഥാനത്തിൽ ഇപ്പോൾ നിങ്ങൾ ഒരു ബൈനറി ട്രീ നിർമ്മിക്കേണ്ടതുണ്ട്. ഓരോ സൂചികയിലും പാരന്റ് നോഡിന്റെ സൂചിക അറേ സംഭരിക്കുന്നു.

ഉദാഹരണം

നൽകിയ രക്ഷാകർതൃ അറേ പ്രാതിനിധ്യത്തിൽ നിന്ന് ബൈനറി ട്രീ നിർമ്മിക്കുക

Inorder Traversal: 3 1 0 4 2 5

സമീപനം

തന്നിരിക്കുന്ന രക്ഷകർത്താവിൽ നിന്ന് ബൈനറി ട്രീ നിർമ്മിക്കാൻ പ്രശ്നം ഞങ്ങളോട് ആവശ്യപ്പെടുന്നു ശ്രേണി പ്രാതിനിധ്യം. ഒരു പാരന്റ് അറേ അറേയുടെ ഓരോ സൂചികയിലും പാരന്റ് നോഡിന്റെ സൂചിക സംഭരിക്കുന്നു. ഇപ്പോൾ നിങ്ങൾ ഈ അറേ ഉപയോഗിച്ച് ഒരു ബൈനറി ട്രീ നിർമ്മിക്കേണ്ടതുണ്ട്. ഇൻപുട്ട് അറേയിലെ മൂല്യം -1 ലെ റൂട്ട് നോഡിനെ സൂചിപ്പിക്കുന്നു വൃക്ഷം.

പുതിയ നോഡുകൾ സൃഷ്ടിക്കുന്നത് തുടരുക എന്നതാണ് നിഷ്കളങ്കമായ സമീപനം. ഈ നോഡുകൾ‌ സൃഷ്‌ടിക്കുമ്പോൾ‌ ഞങ്ങൾ‌ എല്ലായ്‌പ്പോഴും നോഡുകളെ ബൈനറി ട്രീയിൽ‌ ലെവലിന്റെ ക്രമത്തിൽ‌ സൃഷ്‌ടിക്കുന്നു. ഉദാഹരണത്തിന്, ആദ്യം, ഞങ്ങൾ റൂട്ട് സൃഷ്ടിക്കുന്നു, തുടർന്ന് അതിന്റെ കുട്ടികൾ, അങ്ങനെ. ഞങ്ങൾ നോഡുകൾ സൃഷ്ടിക്കുമ്പോൾ പോയിന്ററുകളുടെ പരിഷ്കരണത്തിന്റെ സഹായത്തോടെ ട്രീയിലെ നോഡുകൾ അറ്റാച്ചുചെയ്യുന്നു. എന്നാൽ ഈ സമീപനം കാര്യക്ഷമമല്ല, കാരണം നിലവിൽ സൃഷ്ടിച്ച നോഡിന്റെ രക്ഷകർത്താവിനെ കണ്ടെത്താൻ ഞങ്ങൾ ട്രീയിലൂടെ സഞ്ചരിക്കും.

ഇതിനകം സൃഷ്ടിച്ച നോഡുകളുടെ ട്രാക്ക് സൂക്ഷിക്കുക എന്നതാണ് മികച്ചതും കാര്യക്ഷമവുമായ പരിഹാരം. ഈ രീതിയിൽ നിലവിലെ നോഡിന്റെ രക്ഷകർത്താവിനായി ഞങ്ങൾ തിരയേണ്ടതില്ല. ഈ പരിഹാരം അൽപ്പം വ്യത്യസ്തമാണ്. രക്ഷാകർതൃ നോഡ് സൃഷ്ടിച്ചിട്ടുണ്ടോ എന്ന് ഇവിടെ ആദ്യം പരിശോധിക്കും. ഇത് സൃഷ്ടിച്ചിട്ടുണ്ടെങ്കിൽ അത് നല്ലതാണ്. അല്ലെങ്കിൽ, ഞങ്ങൾ എല്ലാ രക്ഷാകർതൃ നോഡുകളും ആവർത്തിച്ച് സൃഷ്ടിക്കുകയും തുടർന്ന് ചൈൽഡ് നോഡ് സൃഷ്ടിക്കുകയും ചെയ്യുന്നു. ഈ രീതിയിൽ ഞങ്ങൾ പോയിന്റർ പരിഷ്‌ക്കരണത്തിലൂടെ കുട്ടികളുടെ നോഡുകൾ അറ്റാച്ചുചെയ്യുന്നത് തുടരുന്നു.

കോഡ്

നൽകിയ രക്ഷാകർതൃ അറേ പ്രാതിനിധ്യത്തിൽ നിന്ന് ബൈനറി ട്രീ നിർമ്മിക്കുന്നതിനുള്ള സി ++ കോഡ്

#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

നൽകിയ രക്ഷാകർതൃ അറേ പ്രാതിനിധ്യത്തിൽ നിന്ന് ബൈനറി ട്രീ നിർമ്മിക്കാനുള്ള ജാവ കോഡ്

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ ആവർത്തനം ഉപയോഗിക്കുന്നുണ്ടെങ്കിലും. നോഡ് സൃഷ്ടിച്ചിട്ടുണ്ടെങ്കിൽ ഞങ്ങൾ ഒരിക്കലും അതേ നോഡ് സൃഷ്ടിക്കില്ല. അങ്ങനെ സമയപരിധി രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), കാരണം നോഡ് സൃഷ്ടിച്ചിട്ടുണ്ടോ ഇല്ലയോ എന്ന് പരിശോധിക്കാൻ ഞങ്ങൾ ഒരു കൂട്ടം നോഡുകൾ സൃഷ്ടിച്ചു. അങ്ങനെ സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.