বাইনারি গাছের ডায়াগোনাল ট্র্যাভার্সাল


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ফ্যাক্সেট ধর্মান্ধদের ফোরকিটস আকাশবাণী Payu Quora
বাইনারি ট্রি গাছ ট্রি ট্রভারসাল

সমস্যা বিবৃতি

"বাইনারি গাছের ডায়াগোনাল ট্র্যাভারসাল" সমস্যাটি বলে যে আপনাকে একটি বাইনারি গাছ দেওয়া হয়েছে এবং এখন আপনাকে প্রদত্ত গাছটির জন্য তির্যক দৃষ্টিভঙ্গি খুঁজে বের করতে হবে। উপরের-ডান দিক থেকে যখন আমরা একটি গাছ দেখি। যে নোডগুলি আমাদের কাছে দৃশ্যমান তা বাইনারি গাছের তির্যক দৃশ্য।

উদাহরণ

বাইনারি গাছের ডায়াগোনাল ট্র্যাভার্সাল

2 7
3 4
5 6

ব্যাখ্যা

প্রথম তির্যকটি সেখানে 2, 7 নোড রয়েছে। তারপরে দ্বিতীয় তির্যকটি 3, 4 রয়েছে তেমনিভাবে তৃতীয় ত্রি 5, 6 এর জন্য Thus. সুতরাং আউটপুট এমনভাবে মুদ্রিত হয়েছে যাতে একই তির্যকটি থেকে থাকা উপাদানগুলি একই লাইনে থাকে।

অভিগমন

বাইনারি গাছের ডায়াগোনাল ট্র্যাভার্সাল

সমস্যাটি আমাদের উপরে ডান দিক থেকে দৃশ্যমান নোডগুলি মুদ্রণ করতে বলে। তাহলে আমরা কীভাবে সমস্যার সমাধান করব?

আমরা বাইনারি গাছের একটি অভ্যন্তরীণ ট্রভারসাল করব। এটি করার সময়, আমরা একটি তির্যক দিক থেকে দূরত্বটি ট্র্যাক করব। যখনই আমরা বাম দিকে অগ্রসর করি আমরা তির্যক দূরত্বে 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]

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এনলগএন), কারণ আমরা গাছটিকে পিছনে ফেলেছি এবং মানগুলি আপডেট করেছি। কারণ আমরা একটি মানচিত্র ব্যবহার করেছি, সন্নিবেশ, মুছে ফেলা এবং অনুসন্ধান ও (লগএন) সময়ে করা হয়েছে।

স্পেস জটিলতা ity

চালু), কারণ আমরা মানচিত্রে সমস্ত নোড সংরক্ষণ করছি। স্থান জটিলতা রৈখিক।