ബൈനറി ട്രീയുടെ ഡയഗണൽ ട്രാവെർസൽ


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫാക്റ്റ്സെറ്റ് ഫനാറ്റിക്സ് ഫോർകൈറ്റുകൾ ഒറാക്കിൾ പേ Quora
ബൈനറി ട്രീ വൃക്ഷം ട്രീ ട്രാവെർസൽ

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

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

ഉദാഹരണം

ബൈനറി ട്രീയുടെ ഡയഗണൽ ട്രാവെർസൽ

2 7
3 4
5 6

വിശദീകരണം

ആദ്യത്തെ ഡയഗണലിന് 2, 7 നോഡുകൾ ഉണ്ട്. രണ്ടാമത്തെ ഡയഗണലിന് 3, 4 ഉണ്ട്, സമാനമായി മൂന്നാമത്തെ ഡയഗണൽ 5, 6 ന് സമാനമാണ്. അങ്ങനെ output ട്ട്‌പുട്ട് ഒരേ ഡയഗണലിലെ മൂലകങ്ങൾ ഒരേ വരിയിൽ ഉള്ള രീതിയിൽ അച്ചടിക്കുന്നു.

സമീപനം

ബൈനറി ട്രീയുടെ ഡയഗണൽ ട്രാവെർസൽ

മുകളിൽ വലത് ദിശയിൽ നിന്ന് നമുക്ക് ദൃശ്യമാകുന്ന നോഡുകൾ പ്രിന്റുചെയ്യാൻ പ്രശ്‌നം ആവശ്യപ്പെടുന്നു. അപ്പോൾ ഞങ്ങൾ എങ്ങനെ പ്രശ്നം പരിഹരിക്കും?

ബൈനറി ട്രീയുടെ ഇൻ‌ഓർ‌ഡർ‌ ട്രാവെർ‌സൽ‌ ഞങ്ങൾ‌ ചെയ്യും. ഇത് ചെയ്യുമ്പോൾ, ഞങ്ങൾ ഒരു ഡയഗണൽ ദിശയിലുള്ള ദൂരം ട്രാക്കുചെയ്യും. നമ്മൾ ഇടത് ദിശയിലേക്ക് നീങ്ങുമ്പോഴെല്ലാം ഡയഗണൽ ദൂരത്തിലേക്ക് 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]

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (NlogN), കാരണം ഞങ്ങൾ ട്രീയിലൂടെ സഞ്ചരിച്ച് മൂല്യങ്ങൾ അപ്‌ഡേറ്റുചെയ്‌തു. ഞങ്ങൾ ഒരു മാപ്പ് ഉപയോഗിച്ചതിനാൽ, ഉൾപ്പെടുത്തൽ, ഇല്ലാതാക്കൽ, തിരയൽ എന്നിവ O (ലോഗ് എൻ) സമയത്താണ് ചെയ്യുന്നത്.

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

O (N), കാരണം ഞങ്ങൾ മാപ്പിൽ എല്ലാ നോഡുകളും സംഭരിക്കുന്നു. സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.