ባለ ሁለትዮሽ ዛፍ ሰያፍ ማቋረጥ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፋርስት አፍቃሪዎች አራት ኪይትስ በ Oracle PayU Quora
ሁለትዮሽ ዛፍ ዛፍ የዛፍ ተሻጋሪ

የችግሩ መግለጫ

ችግሩ “ባለ ሁለትዮሽ ዛፍ ሰያፍ ማቋረጥ” የሚለው የሁለትዮሽ ዛፍ እንደተሰጠዎት እና አሁን ለተሰጠው ዛፍ የሰያፍ እይታን መፈለግ ያስፈልግዎታል ፡፡ ከላይ ከቀኝ አቅጣጫ አንድ ዛፍ ስናይ ፡፡ ለእኛ የሚታዩ አንጓዎች የሁለትዮሽ ዛፍ ሰያፍ እይታ ናቸው ፡፡

ለምሳሌ

ባለ ሁለትዮሽ ዛፍ ሰያፍ ማቋረጥ

2 7
3 4
5 6

ማስረጃ

የመጀመሪያው ሰያፍ እዚያ ውስጥ ኖዶች 2 ፣ 7 አሉት ፡፡ ከዚያ ሁለተኛው ሰያፍ 3 ፣ 4 አለው ፣ በተመሳሳይ ለሶስተኛው ሰያፍ 5 ፣ 6. ስለሆነም ውጤቱ ከአንድ ሰያፍ የሚመጡ አካላት በተመሳሳይ መስመር እንዳሉ በሆነ መንገድ ታትሟል ፡፡

ቀረበ

ባለ ሁለትዮሽ ዛፍ ሰያፍ ማቋረጥ

ችግሩ ከላይ ከቀኝ አቅጣጫ ለእኛ የሚታዩትን አንጓዎች እንድናተም እንድንጠይቅ ይጠይቀናል ፡፡ ስለዚህ ችግሩን እንዴት እንፈታዋለን?

የሁለትዮሽ ዛፍ ውስጠ-ጥሰትን እናከናውናለን። ይህንን እያደረግን ፣ ርቀቱን በዲያግሎክ አቅጣጫ እንከተላለን ፡፡ በግራ አቅጣጫ በምንንቀሳቀስበት በማንኛውም ጊዜ ወደ ሰያፍ ርቀት 1 እንጨምራለን እናም በትክክለኛው አቅጣጫ ከተንቀሳቀስን በርቀቱ ላይ ምንም እሴት አንጨምርም ፡፡ ስለዚህ ፣ ይህንን እያደረግን በ ‹ሀ› ውስጥ የተጎበኙትን አንጓዎች እንከታተላለን ካርታ. ሰያፍ ርቀት እንደ ቁልፍ እና ቬክተር እንደ እሴት ካርታ እንፈጥራለን ፡፡ ምክንያቱም አንጓዎቹን በቬክተር ውስጥ ከሰያፍ ርቀት ጋር እንጨምራለን ፡፡ እና እኛ በአጠቃላይ ውስጥ እንደ ተጓዝን ዛፍ. ከተጓዙ በኋላ አንጓዎቹን በቬክተሮች ውስጥ እንደ ሰያፍ ርቀት እንጠብቃቸው ነበር ፡፡

ከነዚህ ሁሉ ስሌቶች በኋላ አንጓዎቹን ከእያንዳንዱ ቬክተር በመለየት በቀላሉ በካርታው ውስጥ ያሉትን ንጥረ ነገሮች በቀላሉ ያትሙ ፡፡

የሁለትዮሽ ዛፍ ሰያፍ ማቋረጥን ለማተም የ C ++ ኮድ

#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) ጊዜ ውስጥ ተከናውኗል።

የቦታ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም በካርታው ውስጥ ያሉትን ሁሉንም አንጓዎች እናከማቸዋለን። የቦታ ውስብስብነት መስመራዊ ነው።