ഒരു ബൈനറി ട്രീയുടെ ചുവടെയുള്ള കാഴ്ച  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ കൂപ്പൺ‌ഡ്യൂണിയ ഫ്ലിപ്പ്കാർട്ട് Paytm വാൾമാർട്ട് ലാബുകൾ
ബൈനറി ട്രീ വൃക്ഷം ട്രീ ട്രാവെർസൽ

പ്രശ്നം പ്രസ്താവന  

“ഒരു ബൈനറി ട്രീയുടെ ചുവടെയുള്ള കാഴ്ച” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു ബൈനറി ട്രീ നൽകിയിട്ടുണ്ടെന്നും ഇപ്പോൾ നൽകിയതിന്റെ താഴത്തെ കാഴ്ച കണ്ടെത്തേണ്ടതുണ്ടെന്നും പറയുന്നു വൃക്ഷം. താഴേക്കുള്ള ദിശയിൽ നിന്ന് ഒരു മരം കാണുമ്പോൾ. നമുക്ക് കാണാനാകുന്ന നോഡുകൾ ബൈനറി ട്രീയുടെ ചുവടെയുള്ള കാഴ്ചയാണ്.

ഉദാഹരണം  

ഒരു ബൈനറി ട്രീയുടെ ചുവടെയുള്ള കാഴ്ച

5 6 4 7

സമീപനം  

സമീപനം ലളിതമാണ്, കാരണം ഇതിന് സമാനമായ ഒരു പ്രശ്നം ഞങ്ങൾ ഇതിനകം പരിഹരിച്ചു. പ്രശ്നം ഒരു ബൈനറി ട്രീയുടെ ടോപ്പ് വ്യൂ ഇതിന് സമാനമാണ്, മുകളിൽ പറഞ്ഞ ദിശയിൽ നിന്ന് നമുക്ക് ദൃശ്യമാകുന്ന നോഡുകൾ പ്രിന്റുചെയ്യേണ്ടിവന്നു. അപ്പോൾ ഞങ്ങൾ എങ്ങനെ പ്രശ്നം പരിഹരിക്കും?

തിരശ്ചീന ദൂരം എന്ന ആശയം ഞങ്ങൾ ഇവിടെ ഉപയോഗിക്കേണ്ടതുണ്ട്. ഒരു നോഡിന്റെ ഇടത് ദിശയിലേക്ക് നീങ്ങുമ്പോഴെല്ലാം, നിലവിലെ നോഡിന്റെ തിരശ്ചീന ദൂരത്തിൽ നിന്ന് ഞങ്ങൾ കുറയ്ക്കുന്നു. അതുപോലെ, ഞങ്ങൾ ശരിയായ ദിശയിലേക്ക് നീങ്ങുകയാണെങ്കിൽ, തിരശ്ചീന ദൂരത്തേക്ക് 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;
}

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 (ലോഗ് എൻ) സമയത്താണ് ചെയ്യുന്നത്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), പരമാവധി ലെവലിൽ (N + 1) / 2 ഉണ്ടാകാം. അങ്ങനെ സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.