बाइनरी रूखको तल दृश्य


कठिनाई तह सजिलो
बारम्बार सोधिन्छ समग्र अमेजन कुपनडुनिया फ्लिपकार्ट पेटम वालमार्ट ल्याबहरू
बाइनरी रूख ट्री रूख ट्राभर्सल

समस्या वक्तव्य

समस्या "बाइनरी रूखको तल दृश्य" भन्छन कि तपाईंलाई बाइनरी रूख दिइन्छ र अब तपाईंले तलको दृश्य फेला पार्न आवश्यक छ रूख। जब हामी तलको दिशाबाट रूख देख्छौं। हामीलाई देखिने नोडहरू बाइनरी रूखको तल्लो दृश्य हो।

उदाहरणका

बाइनरी रूखको तल दृश्य

5 6 4 7

दृष्टिकोण

दृष्टिकोण सरल छ किनकि हामीले यस भन्दा पहिले नै समस्या हल गरिसकेका छौं। समस्या बाइनरी रूखको शीर्ष दृश्य योसँग मिल्दो छ जहाँ हामीले नोडहरू प्रिन्ट गर्नुपर्‍यो जुन माथिको दिशाबाट हामीलाई देखिने छ। त्यसोभए हामी कसरी समस्या समाधान गर्छौं?

हामीले तेर्सो दूरीको अवधारणा यहाँ प्रयोग गर्न आवश्यक छ। जब हामी नोडको बाँया दिशामा सर्छौं, हामी हालको नोडको तेर्सो दूरीबाट घटाउँछौं। त्यस्तै, यदि हामी सहि दिशामा सर्छौं भने, हामी तेर्सो दूरीमा १ थप्छौं। एकचोटि हामी यो अवधारणासँग परिचित छौं। हामी प्रत्येक क्षैतिज दूरीमा नोडहरूको ट्र्याक राख्न नक्शा प्रयोग गर्ने छौं। त्यसो भए हामीले रूखलाई ट्रान्सपोर्ट गर्नेछौं र हामीले कुनै नोड फेला पार्दा हामी हाम्रो नक्सा अपडेट गर्दछौं। हामी क्षैतिज दूरी राख्छौं कुञ्जी र नोडमा मानचित्रको मानको रूपमा। त्यसैले एक स्तर अर्डर traversal को प्रयोग गरेर, तेर्सो दूरीको गणना गरी राख्नुहोस् र अपडेट गर्दै नक्सा.

यी सबै गणना पछि, केवल नक्सामा तत्वहरू प्रिन्ट गर्नुहोस्। किनभने सबैभन्दा बाँया नोड सबैभन्दा नकारात्मक तेर्सो दूरीको साथ हुन्छ र दायाँ नोडमा उच्चतम सकारात्मक मान हुन्छ।

C ++ कोड बाइनरी रूखको तल दृश्य प्रिन्ट गर्न

#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), किनकि हामीले रूखलाई ट्र्याभ गरेका छौं र मानहरू अपडेट गरेका छौं। किनकि हामीले नक्सा, ईन्सर्टेशन, मेटाउने प्रयोग गर्‍यौं, र खोज O (logN) समयमा गरियो।

ठाउँ जटिलता

O (N), अधिकतम अन्तिम स्तरमा (N + 1) / २ हुन सक्दछ। यसैले ठाउँ जटिलता रैखिक छ।