የሁለትዮሽ ዛፍ የታችኛው እይታ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ አማዞን ኩፖንዱኒያ Flipkart Paytm የዎልማርት ላብራቶሪዎች
ሁለትዮሽ ዛፍ ዛፍ የዛፍ ተሻጋሪ

የችግሩ መግለጫ

ችግሩ “የሁለትዮሽ ዛፍ የታችኛው እይታ” የሁለትዮሽ ዛፍ እንደተሰጠዎት እና አሁን ለተሰጡት የታችኛው እይታ መፈለግ አለብዎት ዛፍ. አንድን ዛፍ ወደታች አቅጣጫ ስንመለከት. ለእኛ የሚታዩ አንጓዎች የሁለትዮሽ ዛፍ የታችኛው እይታ ናቸው ፡፡

ለምሳሌ

የሁለትዮሽ ዛፍ የታችኛው እይታ

5 6 4 7

ቀረበ

ከዚህ ጋር ተመሳሳይ የሆነ ችግር ቀድሞውኑ ስለፈታነው አካሄዱ ቀላል ነው ፡፡ ችግሩ የሁለትዮሽ ዛፍ የላይኛው እይታ ከላይ ከተጠቀሰው አቅጣጫ ለእኛ የሚታዩትን አንጓዎች ማተም ከነበረብን ከዚህ ጋር ተመሳሳይ ነው ፡፡ ስለዚህ ችግሩን እንዴት እንፈታዋለን?

አግድም የርቀት ፅንሰ-ሀሳብ እዚህ ላይ መጠቀም ያስፈልገናል ፡፡ በመስቀለኛ ክፍል በግራ አቅጣጫ በምንንቀሳቀስበት ጊዜ ሁሉ ከአሁኑ የመስቀለኛ ክፍል አግድም ርቀት እንቀንሳለን ፡፡ በተመሳሳይ ሁኔታ በትክክለኛው አቅጣጫ የምንጓዝ ከሆነ 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;
}

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (NlogN)፣ ዛፉን ስለ ተሻገርነው እና እሴቶቹን አዘምነናል። ምክንያቱም ካርታ ስለተጠቀምን ማስገባት ፣ መሰረዝ እና ፍለጋ በ O (logN) ጊዜ ውስጥ ተከናውኗል።

የቦታ ውስብስብነት

ኦ (ኤን)፣ በመጨረሻው ደረጃ (N + 1) / 2 ሊኖር ይችላል። ስለዚህ የቦታ ውስብስብነት መስመራዊ ነው።