Знайсці абыход BST пасля замовы з папярэдняга абходу  


Узровень складанасці серада
Часта пытаюцца ў амазонка Фуркайты PayU
Двайковае дрэва пошуку Абход дрэва

Пастаноўка праблемы  

Праблема «Знайсці абыход BST пасля замовы» абвяшчае, што вам дадзена абыход папярэдняга заказу двайковага дрэва пошуку. Затым з дапамогай дадзенага ўводу знайдзіце пераход пасля ўпарадкавання.

Прыклад  

Знайсці абыход BST пасля замовы з папярэдняга абходуPin  

preorder traversal sequence: 5 2 1 3 4 7 6 8 9
1 4 3 2 6 9 8 7 5

Падыход  

Дадзеная праблема кажа пра тое, што нам прадастаўляецца паслядоўнасць абыходу папярэдняга заказу двайковага дрэва пошуку. Цяпер нам трэба знайсці абход дрэва з паслядоўным упарадкаваннем, які мае такі ж абход перадзаказу, як і ўваход. Ад нас патрабуецца эфектыўна вырашыць гэтую праблему.

Наіўны падыход - гэта спачатку выкарыстаць предпорядок абход і пабудаваць BST. Тады проста зрабіце абход пасля замовы па гэтым нядаўна пабудаваным дрэве. Але такі падыход неэфектыўны ў дачыненні да прасторы. Паколькі пабудаванае дрэва дзейнічае як накладныя выдаткі.

Для эфектыўнага вырашэння праблемы мы праходзім масіў уводу. Уваходны масіў - гэта наш абход папярэдняга заказу. Такім чынам, мы праходзім пераход перад замовай і знаходзім, ці павінен ляжаць бягучы элемент. Калі мы пачынаем з першага элемента, мы ўсталёўваем дыяпазон ад мінімальнага цэлага значэння да максімальнага цэлага значэння. Паколькі абход папярэдняга заказу мае корань перад левым і правым паддрэвам. Мы ведаем, што калі левае паддрэва існуе, то элементы павінны ляжаць ад мінімальнага цэлага значэння да значэння, меншага за корань. Аналагічна для правага паддрэва, якое павінна ляжаць ад значэння большага кораня да максімальнага цэлага значэння. Цяпер, калі бягучы элемент не знаходзіцца ў гэтым дыяпазоне. Тады гэта павінна ляжаць у іншым паддрэве (гэта значыць, калі яно не знаходзіцца ў дыяпазоне для левага паддрэва, чым павінна знаходзіцца ў правым паддрэве і наадварот).

Глядзіце таксама
Знайдзіце максімальную суму ўзроўню ў двайковым дрэве

код  

Код C ++ для пошуку абыходу BST пасля замовы з папярэдняга абыходу

#include<bits/stdc++.h>
using namespace std;

void preToPost(int input[], int n, int mn, int mx, int& idx)
{
  // base case
  if (idx == n)
    return;
  // if current element does not belong to current subtree
  if (input[idx] < mn || input[idx] > mx) {
    return;
  }

  // store the value of root ro print after printing its subtrees
  int root = input[idx];
  idx++;

  // recursively solve for left and right subtree
  preToPost(input, n, mn, root, idx);
  preToPost(input, n, root, mx, idx);
  // print root
  cout<<root<<" ";
}

int main()
{
  int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
  int n = (sizeof input)/(sizeof input[0]);
  int idx = 0;
  	preToPost(input, n, INT_MIN, INT_MAX, idx);
}
1 4 3 2 6 9 8 7 5

Код Java для пошуку абыходу BST пасля замовы з папярэдняга абыходу

import java.util.*;

class Main{
  static int idx = 0;
  static void preToPost(int input[], int n, int mn, int mx)
  {
    // base case
    if (idx == n)
      return;
    // if current element does not belong to current subtree
    if (input[idx] < mn || input[idx] > mx) {
      return;
    }

    // store the value of root ro print after printing its subtrees
    int root = input[idx];
    idx++;

    // recursively solve for left and right subtree
    preToPost(input, n, mn, root);
    preToPost(input, n, root, mx);
    // print root
    System.out.print(root+" ");
  }

  public static void main(String[] args)
  {
    int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
    int n = input.length;
    	preToPost(input, n, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
}
1 4 3 2 6 9 8 7 5

Аналіз складанасці  

Складанасць часу

O (N), таму што мы павінны прайсці ўвесь дадзены масіў.

Касмічная складанасць

O (N), з-за стэка кампілятара, які выкарыстоўваецца для рэкурсіўных функцый.