द्विआधारी वृक्ष के विकर्ण ट्रावर्सल


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना FactSet कट्टरपंथियों चौपाई ओरेकल PayU Quora
बाइनरी ट्री पेड़ वृक्ष का त्राटक

समस्या का विवरण

समस्या "बाइनरी ट्री के विकर्ण ट्रैवर्सल" कहती है कि आपको एक बाइनरी ट्री दिया जाता है और अब आपको दिए गए ट्री के लिए विकर्ण दृश्य खोजने की आवश्यकता है। जब हम शीर्ष-सही दिशा से एक पेड़ देखते हैं। जो नोड्स हमें दिखाई दे रहे हैं वह बाइनरी ट्री का विकर्ण दृश्य है।

उदाहरण

द्विआधारी वृक्ष के विकर्ण ट्रावर्सल

2 7
3 4
5 6

व्याख्या

पहले विकर्ण में 2, 7 नोड होते हैं। फिर दूसरे विकर्ण में 3, 4 है, इसी तरह तीसरे विकर्ण 5, 6 के लिए। इस प्रकार आउटपुट को इस तरह से प्रिंट किया गया है कि एक ही विकर्ण के तत्व एक ही पंक्ति में हैं।

दृष्टिकोण

द्विआधारी वृक्ष के विकर्ण ट्रावर्सल

समस्या हमें उन नोड्स को प्रिंट करने के लिए कहती है जो शीर्ष-दाईं दिशा से हमें दिखाई देते हैं। तो हम समस्या को कैसे हल करते हैं?

हम बाइनरी ट्री के इनवर्टर ट्रैवर्सल करेंगे। ऐसा करते समय, हम एक विकर्ण दिशा में दूरी का ट्रैक रखेंगे। जब भी हम बाईं दिशा में आगे बढ़ते हैं तो हम 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 diagonalView(node* root, int dis, map<int, vector<int>> &m){
    if(root){
        m[dis].push_back(root->data);
        // move in the left direction with dis+1 distance
        diagonalView(root->left, dis+1, m);
        // move in the right direction with dis distance
        diagonalView(root->right, dis, m);
    }
}

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, vector<int>> m;
    diagonalView(root, 0, m);
    for(auto x: m){
        for(auto nodes: x.second)
            cout<<nodes<<" ";
        cout<<endl;
    }
}
2 7
3 4
5 6

बाइनरी ट्री के विकर्ण ट्रैवर्सल को प्रिंट करने के लिए जावा कोड

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 diagonalView(node root, int dis, Map<Integer, Vector<Integer>> m){
      if(root != null){
      	Vector<Integer> v = m.get(dis);
      	if(v == null){
      		v = new Vector<Integer>();
      		v.add(root.data);
      	}
      	else
      		v.add(root.data);
          m.put(dis, v);
          // move in the left direction with dis+1 distance
          diagonalView(root.left, dis+1, m);
          // move in the right direction with dis distance
          diagonalView(root.right, dis, m);
      }
  }

  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, Vector<Integer>> m = new TreeMap<Integer, Vector<Integer>>();
      diagonalView(root, 0, m);
      for(Map.Entry<Integer, Vector<Integer>> entry : m.entrySet())
          System.out.println(entry.getValue());
  }
}
[2, 7]
[3, 4]
[5, 6]

जटिलता विश्लेषण

समय जटिलता

O (NlogN), क्योंकि हमने पेड़ का पता लगाया है और मूल्यों को अद्यतन किया है। क्योंकि हमने मानचित्र, प्रविष्टि, विलोपन का उपयोग किया है और खोज O (logN) समय में की गई है।

अंतरिक्ष जटिलता

पर), क्योंकि हम नक्शे में सभी नोड्स संग्रहीत कर रहे हैं। अंतरिक्ष की जटिलता रैखिक है।