દ્વિસંગી ઝાડની નીચેનું દૃશ્ય


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

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

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

ઉદાહરણ

દ્વિસંગી ઝાડની નીચેનું દૃશ્ય

5 6 4 7

અભિગમ

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

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

આ બધી ગણતરીઓ પછી, ફક્ત નકશામાં તત્વો છાપો. કારણ કે સૌથી ડાબું નોડ એ મોટાભાગના નકારાત્મક આડા અંતર સાથે હોય છે અને જમણી બાજુનો નોડ સૌથી વધુ સકારાત્મક મૂલ્ય ધરાવે છે.

દ્વિસંગી ઝાડનું નીચેનું દૃશ્ય છાપવા માટે સી ++ કોડ

#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;
}

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);

    map<int,int> m;
    queue<pair<int,node*>> q;
    q.push(make_pair(0, root));
    m[0] = root->data;
    while(!q.empty()){
        pair<int, node*> now = q.front();
        q.pop();

        m[now.first] = now.second->data;
        if(now.second->left)
        q.push(make_pair(now.first - 1, now.second->left));
        if(now.second->right)
        q.push(make_pair(now.first + 1, now.second->right));
    }
    for(auto x: m)
        cout<<x.second<<" ";
}
5 6 4 7

બાઈનરી ટ્રીનો બોટમ વ્યુ પ્રિન્ટ કરવા માટે જાવા કોડ

import java.util.*;

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

class Main{

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

  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);

      Map<Integer, Integer> m = new TreeMap<Integer, Integer>();
      Queue<node> q = new LinkedList<node>();
      q.add(root);
      m.put(root.hd, root.data);
      while(!q.isEmpty()){
          node now = q.remove();

          m.put(now.hd, now.data);
          if(now.left != null){
          	now.left.hd = now.hd - 1;
          	q.add(now.left);
          }
          if(now.right != null){
          	now.right.hd = now.hd + 1;
          	q.add(now.right);
          }
      }
      for(Map.Entry<Integer, Integer> entry : m.entrySet())
          System.out.print(entry.getValue()+" ");
  }
}
5 6 4 7

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

સમય જટિલતા

O (NlogN), કારણ કે અમે ઝાડને વટાવ્યું છે અને મૂલ્યોને અપડેટ કર્યા છે. કારણ કે આપણે નકશો, નિવેશ, કાtionી નાખવા અને શોધનો ઉપયોગ ઓ (લોગએન) સમયમાં કર્યો છે.

અવકાશ જટિલતા

ઓ (એન), ઓછામાં ઓછા છેલ્લા સ્તરમાં (એન + 1) / 2 હોઈ શકે છે. આમ જગ્યા જટિલતા રેખીય છે.