Знайти обхід BST після замовлення


Рівень складності Medium
Часто запитують у Амазонка Фуркіти PayU
Бінарне дерево пошуку Обхід дерева

Постановка проблеми

У проблемі "Знайти обхід BST після замовлення" з обробки попереднього замовлення "зазначено, що вам надано обхід попереднього замовлення бінарного дерева пошуку. Потім, використовуючи дані, знайдіть обхід після замовлення.

Приклад

Знайти обхід BST після замовлення

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), через стек компілятора, який використовується для рекурсивних функцій.