Əvvəlcədən sifariş keçidindən BST-nin postorder keçidini tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Fourkites PayU
İkili Axtarış Ağacı Ağacın keçidiBaxılıb 22

Problem bəyanat

Problem "BST-nin post sifariş keçidini əvvəlcədən sifariş keçidindən tapın" problemi sizə ikili axtarış ağacının ön sifariş keçidi verildiyini bildirir. Sonra verilmiş girişdən istifadə edərək poçt postunun keçidini tapın.

misal

Əvvəlcədən sifariş keçidindən BST-nin postorder keçidini tapınPin

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

Yanaşma

Verilən problem bizə ikili axtarış ağacının əvvəlcədən sifariş keçid ardıcıllığı ilə təmin olunduğunu söyləyir. İndi giriş ilə eyni ön sifariş keçidinə sahib olan ağacın postorder keçidini tapmağımız tələb olunur. Bu problemi səmərəli həll etməyimiz tələb olunur.

Sadəlövh yanaşma əvvəlcə istifadə etməkdir ön sifariş keçmək və qurmaq BST. Sonra sadəcə bu yeni tikilmiş ağac üzərində bir postorder traversal edin. Lakin bu yanaşma məkanla bağlı səmərəsizdir. Çünki tikilmiş ağac yerüstü yük kimi çıxış edir.

Problemi səmərəli həll etmək üçün giriş massivindən keçirik. Giriş seriyası əvvəlcədən sifarişimizdir. Beləliklə, əvvəlcədən sifariş keçidindən keçərək mövcud elementin yalan olub-olmadığını tapırıq. Birinci elementlə başlayanda minimum tam ədədi dəyərindən maksimum tam ədədi dəyərinə qədər bir sıra təyin edirik. Çünki əvvəlcədən sifariş keçidinin kökü sol və sağ alt ağacdan əvvəldir. Bilirik ki, sol alt ağac varsa, elementlər minimum tam dəyərdən kökdən kiçik bir dəyərə qədər uzanmalıdır. Eynilə daha böyük kök dəyərindən maksimum tam ədədə qədər olan sağ alt ağac üçün. İndi cari element bu aralıqda deyilsə. O zaman bu, digər alt ağacda olmalıdır (yəni sağ alt ağacda və əksinə, sol alt ağac üçün aralıqda deyilsə).

Kodu

Əvvəlcədən sifariş keçidindən BST-nin postorder keçidini tapmaq üçün C ++ kodu

#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

Əvvəlcədən sifariş keçidindən BST-nin postorder keçidini tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki verilən massivin hamısını keçməliyik.

Kosmik Mürəkkəblik

O (N), rekursiv funksiyalar üçün istifadə olunan kompilyator yığını səbəbindən.

Translate »