ორობითი ხის ქვედა ხედი


Რთული ტური Easy
ხშირად ეკითხებიან თანამოსაყრელი Amazon კუპონი დუნია Flipkart Paytm Walmart Labs
ორობითი ხე ხე ხის გადაკვეთა

პრობლემის განცხადება

პრობლემა ”ორობითი ხის ქვედა ხედი” აცხადებს, რომ თქვენ გეძლევათ ორობითი ხე და ახლა უნდა მოძებნოთ მოცემული ქვედა ხედი. ხე. როდესაც ჩვენ დაღმავალი მიმართულებით ვხედავთ ხეს. ჩვენთვის ხილული კვანძები წარმოადგენს ორობითი ხის ქვედა ხედს.

მაგალითი

ორობითი ხის ქვედა ხედი

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

სირთულის ანალიზი

დროის სირთულე

O (NlogN), რადგან ჩვენ ხე გადავკვეთეთ და განვაახლეთ მნიშვნელობები. იმის გამო, რომ ჩვენ გამოვიყენეთ რუკა, ჩასმა, წაშლა და ძებნა O (logN) დროში ხდება.

სივრცის სირთულე

O (N)მაქსიმუმ შეიძლება იყოს (N + 1) / 2 ბოლო დონეზე. ამრიგად, სივრცის სირთულე ხაზოვანია.