बायनरी ट्रीचे कर्ण ट्रॅव्हर्सल


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

समस्या विधान

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

उदाहरण

बायनरी ट्रीचे कर्ण ट्रॅव्हर्सल

2 7
3 4
5 6

स्पष्टीकरण

पहिल्या कर्णात तेथे नोड्स 2, 7 आहेत. तर दुसर्‍या कर्णात,, 3 असतात, त्याचप्रमाणे तिस third्या कर्ण Thus, 4. साठी. अशा प्रकारे आउटपुटमध्ये अशा प्रकारे छापले गेले आहे की त्याच कर्णातील घटक समान रेषेत आहेत.

दृष्टीकोन

बायनरी ट्रीचे कर्ण ट्रॅव्हर्सल

समस्या आम्हाला वर-उजवीकडून दिसेल अशा नोड्स मुद्रित करण्यास सांगते. मग आम्ही समस्येचे निराकरण कसे करू?

आम्ही बायनरी झाडाची एक अंतर्गत ट्रॅवर्सल करू. हे करत असताना, आम्ही कर्ण दिशेने अंतराचा मागोवा ठेवू. जेव्हा जेव्हा आम्ही डाव्या दिशेने जातो तेव्हा आपण कर्ण अंतरात 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]

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

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

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

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

ओ (एन), कारण आम्ही नकाशामध्ये सर्व नोड्स संचयित करत आहोत. जागेची जटिलता रेखीय आहे.