बायनरी झाडाचे तळाशी दृश्य


अडचण पातळी सोपे
वारंवार विचारले एकत्रित ऍमेझॉन कूपनडुनिया फ्लिपकार्ट पेटीएम वॉलमार्ट लॅब
बायनरी ट्री झाड ट्री ट्रॅव्हर्सल

समस्या विधान

“बायनरी ट्रीचे तळाशी दृश्य” ही समस्या सांगते की आपल्याला बायनरी ट्री दिली गेली आहे आणि आता आपल्याला खाली दिलेले दृश्य शोधण्याची आवश्यकता आहे झाड. जेव्हा आपण खाली दिशेने एक झाड पाहतो. आपल्यास दृश्यमान असलेल्या नोड्स बायनरी झाडाचे तळाशी दृश्य आहे.

उदाहरण

बायनरी झाडाचे तळाशी दृश्य

5 6 4 7

दृष्टीकोन

दृष्टीकोन सोपा आहे कारण आम्ही आधीपासूनच यासारख्या समस्येचे निराकरण केले आहे. बायनरीच्या झाडाची समस्या वरील बाजूस दर्शविली जाते जिथे आम्हाला वरील दिशानिर्देशांद्वारे दृश्यमान नोड्स मुद्रित करावे लागतात. मग आम्ही समस्येचे निराकरण कसे करू?

आपल्याला येथे क्षैतिज अंतराची संकल्पना वापरण्याची आवश्यकता आहे. जेव्हा आपण एखाद्या नोडच्या डाव्या दिशेने जाऊ तेव्हा आम्ही वर्तमान नोडच्या क्षैतिज अंतरापासून वजा करतो. त्याचप्रमाणे, जर आपण योग्य दिशेने गेलो तर आम्ही आडव्या अंतरात 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;
}

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एनएलजीएन), कारण आम्ही झाडाला आडवे केले आहे आणि मूल्ये अद्यतनित केली आहेत. कारण आम्ही नकाशा वापरणे, समाविष्ट करणे, हटविणे आणि शोध ओ (लॉगएन) वेळेत केले आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), किमान पातळीवर (एन + 1) / 2 असू शकतात. अशा प्रकारे स्पेस कॉम्प्लेक्सिटी रेखीय असते.