Дното на дното на бинарното дрво


Ниво на тешкотија Лесно
Често прашувано во Аколит Амазон КупонДунија Flipkart Исплата Лаборатории Walmart
Бинарно дрво Дрво Преминување на дрвото

Изјава за проблем

Проблемот „Дното на дното на бинарното дрво“ наведува дека ви е дадено бинарно дрво и сега треба да го пронајдете долниот приказ за дадениот дрво. Кога ќе видиме дрво од насока надолу. Јазлите што се видливи за нас е долниот поглед на бинарното дрво.

пример

Дното на дното на бинарното дрво

5 6 4 7

Пристап

Пристапот е едноставен затоа што веќе решивме проблем што е сличен на овој. Проблемот Топ поглед на бинарно дрво е сличен на овој каде што требаше да ги испечатиме јазлите што ни се видливи од горенаведената насока. Па, како да го решиме проблемот?

Тука треба да го искористиме концептот на хоризонтално растојание. Кога и да се движиме во левата насока на јазол, се одземаме од хоризонталното растојание на тековниот јазол. Слично на тоа, ако се движиме во вистинската насока, додаваме 1 на хоризонталното растојание. Откако ќе се запознаеме со овој концепт. Useе користиме мапа за да ги следиме јазлите на секое од хоризонталното растојание. Потоа ќе го поминеме дрвото и секогаш кога ќе најдеме јазол, ја ажурираме нашата мапа. Keepе го задржиме хоризонталното растојание како клуч, а јазолот како вредност на картата. Затоа, користејќи пресек по нивен редослед, продолжете со пресметување на хоризонталното растојание и ажурирање на мапа.

По сите овие пресметки, едноставно отпечатете ги елементите на картата. Бидејќи најлевиот јазол е со најнегативно хоризонтално растојание и најдесниот јазол има најголема позитивна вредност.

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

Java код за печатење на Дното на дното на бинарно дрво

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 на последното ниво. Така, комплексноста на просторот е линеарна.