பைனரி மரத்தின் மூலைவிட்ட பயணம்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் உண்மை வெறியர்கள் ஃபோர்கைட்டுகள் ஆரக்கிள் PayU , Quora
பைனரி மரம் மரம் மரம் பயணம்

சிக்கல் அறிக்கை

“பைனரி மரத்தின் மூலைவிட்ட பயணம்” சிக்கல் உங்களுக்கு ஒரு பைனரி மரம் வழங்கப்பட்டுள்ளது என்றும் இப்போது கொடுக்கப்பட்ட மரத்திற்கான மூலைவிட்டக் காட்சியைக் கண்டுபிடிக்க வேண்டும் என்றும் கூறுகிறது. மேல்-வலது திசையில் இருந்து ஒரு மரத்தைப் பார்க்கும்போது. பைனரி மரத்தின் மூலைவிட்டக் காட்சி நமக்குத் தெரியும் முனைகள்.

உதாரணமாக

பைனரி மரத்தின் மூலைவிட்ட பயணம்

2 7
3 4
5 6

விளக்கம்

முதல் மூலைவிட்டத்தில் 2, 7 முனைகள் உள்ளன. இரண்டாவது மூலைவிட்டத்தில் 3, 4 உள்ளது, இதேபோல் மூன்றாவது மூலைவிட்ட 5, 6 ஐக் கொண்டுள்ளது. இவ்வாறு வெளியீடு ஒரே மூலைவிட்டத்தின் கூறுகள் ஒரே வரிசையில் இருக்கும் வகையில் அச்சிடப்பட்டுள்ளன.

அணுகுமுறை

பைனரி மரத்தின் மூலைவிட்ட பயணம்

மேல்-வலது திசையில் இருந்து நமக்குத் தெரியும் முனைகளை அச்சிட சிக்கல் கேட்கிறது. எனவே பிரச்சினையை எவ்வாறு தீர்ப்பது?

பைனரி மரத்தின் ஒரு ஒழுங்கற்ற பயணத்தை நாங்கள் செய்வோம். இதைச் செய்யும்போது, ​​தூரத்தை ஒரு மூலைவிட்ட திசையில் கண்காணிப்போம். நாம் இடது திசையில் நகரும் போதெல்லாம் மூலைவிட்ட தூரத்திற்கு 1 ஐ சேர்க்கிறோம், சரியான திசையில் நகர்ந்தால் தூரத்திற்கு எந்த மதிப்பையும் சேர்க்க மாட்டோம். எனவே, இதைச் செய்யும்போது, ​​a இல் பார்வையிட்ட முனைகளைக் கண்காணிப்போம் வரைபடம். மூலைவிட்ட தூரத்தை விசையாகவும், திசையன் மதிப்பாகவும் ஒரு வரைபடத்தை உருவாக்குவோம். ஏனெனில் ஒரு திசையனில் மூலைவிட்ட தூரத்துடன் முனைகளைச் சேர்ப்போம். நாம் முழுவதுமாக பயணித்திருப்போம் மரம். பயணத்திற்குப் பிறகு, முனைகளை அவற்றின் மூலைவிட்ட தூரத்திற்கு ஏற்ப திசையன்களில் வைத்திருப்போம்.

இந்த கணக்கீடுகள் அனைத்திற்கும் பிறகு, ஒவ்வொரு திசையன்களிலிருந்தும் முனைகளைப் பிரிக்கும்போது வரைபடத்தில் உள்ள கூறுகளை அச்சிடுக.

பைனரி மரத்தின் மூலைவிட்ட பயணத்தை அச்சிட சி ++ குறியீடு

#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]

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (NlogN), ஏனென்றால் நாங்கள் மரத்தை கடந்து, மதிப்புகளை புதுப்பித்துள்ளோம். நாங்கள் ஒரு வரைபடத்தைப் பயன்படுத்தியுள்ளதால், செருகல், நீக்குதல் மற்றும் தேடல் O (logN) நேரத்தில் செய்யப்படுகிறது.

விண்வெளி சிக்கலானது

ஓ (என்), ஏனெனில் நாங்கள் எல்லா முனைகளையும் வரைபடத்தில் சேமித்து வருகிறோம். விண்வெளி சிக்கலானது நேரியல்.