દ્વિસંગી વૃક્ષનો જમણો દેખાવ છાપો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ભેગા એડોબ એમેઝોન MakeMyTrip સ્નેપડીલ
દ્વિસંગી વૃક્ષ વૃક્ષ વૃક્ષ આડેધડ

સમસ્યા નિવેદન

સમસ્યા "દ્વિસંગી ઝાડનો અધિકાર જુઓ" કહે છે કે તમને બાઈનરી ટ્રી આપવામાં આવે છે. હવે તમારે આ વૃક્ષનો યોગ્ય દૃશ્ય શોધવાની જરૂર છે. અહીં, બાઈનરી ટ્રીનો જમણો દૃષ્ટિકોણ એ છે કે જ્યારે જમણી દિશા તરફ જોવામાં આવે ત્યારે ઝાડ જુએ છે તે પ્રમાણે ક્રમ છાપવા માટે.

ઉદાહરણ

દ્વિસંગી વૃક્ષનો જમણો દેખાવ છાપો

2 7 4 6

સમજૂતી

જો તમે દ્વિસંગી ઝાડને યોગ્ય દિશામાં અવલોકન કરો છો. આપણે ફક્ત નોડ્સ જોવામાં સક્ષમ છીએ જે આઉટપુટમાં છાપવામાં આવે છે. કારણ કે 3 અને 5 ગાંઠો અનુક્રમે 7 અને 4 ની પાછળ છુપાયેલા છે.

દ્વિસંગી ઝાડની જમણી દૃષ્ટિ છાપવા માટેનો અભિગમ

આ સમસ્યામાં, અમારે યોગ્ય દેખાવ જોવાની જરૂર છે દ્વિસંગી વૃક્ષ. સમસ્યાને બે અભિગમોનો ઉપયોગ કરીને ઉકેલી શકાય છે. તેમાંથી એક કતારનો ઉપયોગ કરે છે અને બીજો એક રિકર્ઝનનો ઉપયોગ કરે છે. પ્રથમ, આપણે કતારની મદદથી અભિગમની ચર્ચા કરીશું. તેથી, a નો ઉપયોગ કરીને સમસ્યા હલ કરવા માટે કતાર. અમે દ્વિસંગી ઝાડના મૂળથી પ્રારંભ કરીએ છીએ. ઝાડના દરેક સ્તર માટે, અમે કતારમાં ગાંઠો સ્ટોર કરવાનું ચાલુ રાખીએ છીએ. આગલા સ્તરના ગાંઠો સંગ્રહવા માટે, આપણે વર્તમાન સ્તરના ગાંઠો ઉપરથી પસાર થવું પડશે. તેથી જ્યારે આપણે વર્તમાન સ્તરના ગાંઠો ઉપર પસાર થઈએ છીએ. અમે આ સ્તરે છેલ્લું નોડ છાપો. જ્યારે આપણે ઝાડને જમણી બાજુએથી અવલોકન કરીએ છીએ. એકમાત્ર નોડ જે આપણને દૃશ્યક્ષમ છે તે એક સ્તરે જમણો નોડ છે. આ અભિગમ એક કતારનો ઉપયોગ કરે છે જે જગ્યા લે છે.

ચાલો રિકર્ઝનનો ઉપયોગ કરીને સોલ્યુશનની ચર્ચા કરીએ. ઉકેલો એ ઝાડનો ડાબી દૃશ્ય શોધવામાં સમાન છે. આ અભિગમમાં. અમે ફક્ત ઝાડનું એક આડુંઅવળું કરીએ છીએ જે આંતરિક ક્રમિકની વિરુદ્ધ હોય છે. પરંતુ અમે હાલમાં જે સ્તર પર છીએ તેના પર પણ ધ્યાન રાખીએ છીએ અને અત્યાર સુધી મહત્તમ સ્તર પ્રાપ્ત કર્યું છે. જેમ કે આપણે ડાબી સબટ્રી પહેલા જમણી સબટ્રી ઉપર જઈએ છીએ. જ્યારે પણ આપણે ઝાડમાં નવા સ્તરે પ્રવેશ કરીએ છીએ. અમે પ્રથમ જમણી બાજુના નોડનો સામનો કરીએ છીએ. તેથી અમે હંમેશાં તપાસ ચાલુ રાખીએ છીએ કે શું વર્તમાન સ્તર મહત્તમ સ્તર કરતા વધારે છે, અમે નોડ છાપીશું. જો આપણે કમ્પાઇલર સ્ટેક માટે જરૂરી જગ્યાને ધ્યાનમાં ન લઈએ તો અભિગમ વધુ સારું છે. જો આપણે કમ્પાઇલર સ્ટેક દ્વારા લેવાયેલી જગ્યાને ધ્યાનમાં લઈએ તો સમસ્યાનું અવકાશ જટિલતા ઝાડની heightંચાઇ પર આધારિત છે.

કોડ

દ્વિસંગી વૃક્ષનો જમણો દેખાવ છાપવા માટે સી ++ કોડ

#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 printRightView(node* root, int level, int &max_level){
    if(root){
        if(level > max_level){
            max_level = level;
            cout << root->data <<" ";
        }
        printRightView(root->right, level+1, max_level);
        printRightView(root->left, level+1, max_level);
    }
}

int main(){
  node *root = create(2);
  root->left = create(3);
  root->right = create(7);
  root->left->left = create(5);
  root->left->right =create(4);
  root->left->right->left = create(6);

  int max_level = 0;
  printRightView(root, 1, max_level);
}
2 7 4 6

દ્વિસંગી વૃક્ષનો જમણો દેખાવ છાપવા માટે જાવા કોડ

import java.util.*;

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

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

  static int max_level;
  static void printRightView(node root, int level){
      if(root != null){
          if(level > max_level){
              max_level = level;
              System.out.print(root.data+" ");
          }
          printRightView(root.right, level+1);
          printRightView(root.left, level+1);
      }
  }

  public static void main(String[] args){
    node root = create(2);
    root.left = create(3);
    root.right = create(7);
    root.left.left = create(5);
    root.left.right =create(4);
    root.left.right.left = create(6);
    
    max_level = 0;
    printRightView(root, 1);
  }
}
2 7 4 6

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), અમે ફક્ત ઝાડમાં ગાંઠો વટાવી રહ્યા છીએ. તેથી જો ઝાડમાં એન ગાંઠો હોય, તો અલ્ગોરિધમનો કરવા O (N) ક્રિયાઓ કરવા માટે જરૂરી છે.

અવકાશ જટિલતા

ઓ (1) જો કમ્પાઇલર સ્ટેક દ્વારા વપરાયેલી જગ્યાને ધ્યાનમાં લેવામાં નહીં આવે, નહીં તો ઓ (એચ) જગ્યા જરૂરી છે.