Рубрики

Проверьте идентичные BST без построения деревьев

Даны два массива, которые представляют собой последовательность клавиш. Представьте, что мы создаем дерево двоичного поиска (BST) из каждого массива. Нам нужно сказать, будут ли два BST одинаковыми или нет без фактического построения дерева.

Примеры
Например, входные массивы: {2, 4, 3, 1} и {2, 1, 4, 3} создадут одно и то же дерево

 Let the input arrays be a[] and b[]

Example 1:
a[] = {2, 4, 1, 3} will construct following tree.
   2
 /  \
1    4
    /
   3
b[] = {2, 4, 3, 1} will also also construct the same tree.
   2
 /  \
1    4
    /
   3 
So the output is "True"

Example 2:
a[] = {8, 3, 6, 1, 4, 7, 10, 14, 13}
b[] = {8, 10, 14, 3, 6, 4, 1, 7, 13}

They both construct the same following BST, so output is "True"
            8
         /    \
       3       10
     /  \        \
    1     6       14
        /   \     /
       4     7   13  

Решение:
Согласно свойству BST, элементы левого поддерева должны быть меньше, а элементы правого поддерева должны быть больше, чем корень.
Два массива представляют один и тот же BST, если для каждого элемента x элементы в левом и правом поддеревьях x появляются после него в обоих массивах. И то же самое верно для корней левого и правого поддеревьев.
Идея состоит в том, чтобы проверить, являются ли следующие меньшие и большие элементы одинаковыми в обоих массивах. Те же свойства рекурсивно проверяются для левого и правого поддеревьев. Идея выглядит простой, но реализация требует проверки всех условий для всех элементов. Ниже приводится интересная рекурсивная реализация идеи.

C ++

// Программа на C ++ для проверки идентичных
// BST без построения деревьев
#include <bits/stdc++.h>

using namespace std;

  
/ * Основная функция, которая проверяет, если два
массивы a [] и b [] размера n
тот же BST. Два значения «мин» и «макс»
решить, будет ли сделан звонок для левых
поддерево или правое поддерево родителя
элемент. Индексы i1 и i2 являются
индексы в (a [] и b []), после чего мы
искать левого или правого ребенка. Первоначально,
вызов сделан для INT_MIN и INT_MAX
как 'min' и 'max' соответственно, потому что
Корень не имеет родителя. i1 и i2 просто
после индексов родительского элемента в a [] и b []. * /

bool isSameBSTUtil(int a[], int b[], 

                int n, int i1, int i2,

                    int min, int max) 

int j, k; 

  
/ * Поиск значения, удовлетворяющего
ограничения мин и макс в [] и
б []. Если родительский элемент является листом
узел, то должно быть несколько элементов
в a [] и b [], удовлетворяющих ограничению. * /

for (j = i1; j < n; j++) 

    if (a[j] > min && a[j] < max) 

        break

for (k = i2; k < n; k++) 

    if (b[k] > min && b[k] < max) 

        break

  
/ * Если родительский элемент является листом в обоих массивах * /

if (j==n && k==n) 

    return true

  
/ * Вернуть false, если выполняется любое из следующих условий

    а) Если родительский элемент является листом в одном массиве,

        но без листьев в другом.

    б) Элементы, удовлетворяющие ограничениям

        не то же самое. Мы либо ищем левых

        ребенок или правый ребенок от родителя

        элемент (определяется минимальным и максимальным значениями).

        Найденный ребенок должен быть одинаковым в обоих массивах *

if (((j==n)^(k==n)) || a[j]!=b[k]) 

    return false

  
/ * Сделать текущего потомка родителем и
рекурсивная проверка для левого и правого
поддеревья этого. Обратите внимание, что мы также можем
передать [K] вместо [J], как они
оба одинаковы * /

return isSameBSTUtil(a, b, n, j+1, k+1, a[j], max) && // Правое поддерево

        isSameBSTUtil(a, b, n, j+1, k+1, min, a[j]); // Левое поддерево

  
// Обёртка над isSameBSTUtil ()

bool isSameBST(int a[], int b[], int n) 

return isSameBSTUtil(a, b, n, 0, 0, INT_MIN, INT_MAX); 

  
// Код драйвера

int main() 

    int a[] = {8, 3, 6, 1, 4, 7, 10, 14, 13}; 

    int b[] = {8, 10, 14, 3, 6, 4, 1, 7, 13}; 

    int n=sizeof(a)/sizeof(a[0]); 

    if(isSameBST(a, b, n))

    {

        cout << "BSTs are same";

    }

    else

    {

        cout << "BSTs not same";

    }

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// Программа AC для проверки идентичных BST без построения деревьев
#include<stdio.h>
#include<limits.h>
#include<stdbool.h>

  
/ * Основная функция, которая проверяет, являются ли два массива a [] и b [] конструкции размера n

  тот же BST. Два значения 'min' и 'max' определяют, сделан ли вызов для

  левое поддерево или правое поддерево родительского элемента. Индексы i1 и i2

  индексы в (a [] и b []), после чего мы ищем левого или правого потомка.

  Первоначально, вызов сделан для INT_MIN и INT_MAX как 'min' и 'max'

  соответственно, потому что root не имеет родителя.

  i1 и i2 сразу после индексов родительского элемента в a [] и b []. * /

bool isSameBSTUtil(int a[], int b[], int n, int i1, int i2, int min, int max)

{

   int j, k;

  

   / * Поиск значения, удовлетворяющего ограничениям min и max в [] и

      б []. Если родительский элемент является листовым узлом, то должно быть несколько

      элементы в a [] и b [], удовлетворяющие ограничению. * /

   for (j=i1; j<n; j++)

       if (a[j]>min && a[j]<max)

           break;

   for (k=i2; k<n; k++)

       if (b[k]>min && b[k]<max)

           break;

  

   / * Если родительский элемент является листом в обоих массивах * /

   if (j==n && k==n)

       return true;

  

   / * Вернуть false, если выполняется любое из следующих условий

      a) Если родительский элемент является листовым в одном массиве, но не листовым в другом.

      б) Элементы, удовлетворяющие ограничениям, не одинаковы. Мы либо ищем

         для левого или правого потомка родительского элемента (определяется min

         и максимальные значения). Найденный ребенок должен быть одинаковым в обоих массивах *

   if (((j==n)^(k==n)) || a[j]!=b[k])

       return false;

  

   / * Сделать текущего потомка родителем и рекурсивно проверять левый и правый

      поддеревья этого. Обратите внимание, что мы также можем передать [k] вместо a [j], так как они

      оба одинаковы * /

   return isSameBSTUtil(a, b, n, j+1, k+1, a[j], max) &&  // Правое поддерево

          isSameBSTUtil(a, b, n, j+1, k+1, min, a[j]);    // Левое поддерево

}

  
// Обёртка над isSameBSTUtil ()

bool isSameBST(int a[], int b[], int n)

{

   return isSameBSTUtil(a, b, n, 0, 0, INT_MIN, INT_MAX);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

   int a[] = {8, 3, 6, 1, 4, 7, 10, 14, 13};

   int b[] = {8, 10, 14, 3, 6, 4, 1, 7, 13};

   int n=sizeof(a)/sizeof(a[0]);

   printf("%s\n", isSameBST(a, b, n)?

             "BSTs are same":"BSTs not same");

   return 0;

}

Джава

// Java-программа для проверки на идентичность
// BST без построения деревьев

class GFG 

{

  
/ * Основная функция, которая проверяет
если два массива a [] и b [] размера
Русская конструкция та же BST. Два значения
«min» и «max» решают, является ли
вызов сделан для левого поддерева или
правое поддерево родительского элемента.
Индексы i1 и i2 являются индексами
в (a [] и b []), после чего мы ищем
левый или правый ребенок. Первоначально
вызов сделан для INT_MIN и INT_MAX как
'min' и 'max' соответственно, потому что
Корень не имеет родителя. i1 и i2 просто
после индексов родительского элемента в a [] и b []. * /

static boolean isSameBSTUtil(int a[], int b[], int n,

                        int i1, int i2, int min, int max)

{

    int j, k;

  

    / * Поиск значения, удовлетворяющего

    ограничения мин и макс в [] и

    б []. Если родительский элемент является листом

    узел, то должно быть несколько элементов

    в a [] и b [], удовлетворяющих ограничению. * /

    for (j = i1; j < n; j++)

    if (a[j] > min && a[j] < max)

        break;

    for (k = i2; k < n; k++)

        if (b[k] > min && b[k] < max)

            break;

  

    / * Если родительский элемент

    лист в обоих массивах * /

    if (j == n && k == n)

        return true;

  

    / * Вернуть false, если выполняется любое из следующих условий

    а) Если родительский элемент является листом в

    один массив, но не лист в другом.

    б) элементы, удовлетворяющие ограничениям

    не то же самое. Мы либо ищем левых

    дочерний или правый дочерний элемент родительского элемента

    (определяется минимальным и максимальным значениями). Ребенок

    найдено должно быть одинаковым в обоих массивах * /

    if (((j==n)^(k==n)) || a[j]!=b[k])

        return false;

  

    / * Сделать текущего потомка родителем и

    рекурсивная проверка для левого и правого

    поддеревья этого. Обратите внимание, что мы также можем

    передать [K] вместо [J], как они

    оба одинаковы * /

    return isSameBSTUtil(a, b, n, j+1, k+1, a[j], max) && // Правое поддерево

            isSameBSTUtil(a, b, n, j+1, k+1, min, a[j]); // Левое поддерево

}

  
// Обёртка над isSameBSTUtil ()

static boolean isSameBST(int a[], int b[], int n)

{

    return isSameBSTUtil(a, b, n, 0, 0

                    Integer.MIN_VALUE,Integer.MAX_VALUE);

}

  
// Код драйвера

public static void main(String[] args) 

{

    int a[] = {8, 3, 6, 1, 4, 7, 10, 14, 13};

    int b[] = {8, 10, 14, 3, 6, 4, 1, 7, 13};

    int n=a.length;

    System.out.printf("%s\n", isSameBST(a, b, n)?

                "BSTs are same":"BSTs not same");

}
}

  
/ * Этот код предоставлен PrinciRaj1992 * /

C #

// C # программа для проверки на идентичность
// BST без построения деревьев

using System;

  

class GFG 

  
/ * Основная функция, которая проверяет
если два массива a [] и b [] размера
Русская конструкция та же BST. Два значения
«min» и «max» решают, является ли
вызов сделан для левого поддерева или
правое поддерево родительского элемента.
Индексы i1 и i2 являются индексами
в (a [] и b []), после чего мы ищем
левый или правый ребенок. Первоначально
вызов сделан для INT_MIN и INT_MAX как
'min' и 'max' соответственно, потому что
Корень не имеет родителя. i1 и i2 просто
после индексов родительского элемента в a [] и b []. * /

static bool isSameBSTUtil(int []a, int []b, int n, 

                        int i1, int i2, int min, int max) 

    int j, k; 

  

    / * Поиск значения, удовлетворяющего

    ограничения мин и макс в [] и

    б []. Если родительский элемент является листом

    узел, то должно быть несколько элементов

    в a [] и b [], удовлетворяющих ограничению. * /

    for (j = i1; j < n; j++) 

    if (a[j] > min && a[j] < max) 

        break

    for (k = i2; k < n; k++) 

        if (b[k] > min && b[k] < max) 

            break

  

    / * Если родительский элемент

    лист в обоих массивах * /

    if (j == n && k == n) 

        return true

  

    / * Вернуть false, если выполняется любое из следующих условий

    а) Если родительский элемент является листом в

    один массив, но не лист в другом.

    б) элементы, удовлетворяющие ограничениям

    не то же самое. Мы либо ищем левых

    дочерний или правый дочерний элемент родительского элемента

    (определяется минимальным и максимальным значениями). Ребенок

    найдено должно быть одинаковым в обоих массивах * /

    if (((j == n)^(k == n)) || a[j] != b[k]) 

        return false

  

    / * Сделать текущего потомка родителем и

    рекурсивная проверка для левого и правого

    поддеревья этого. Обратите внимание, что мы также можем

    передать [K] вместо [J], как они

    оба одинаковы * /

    return isSameBSTUtil(a, b, n, j + 1, k + 1, a[j], max) && // Правое поддерево

            isSameBSTUtil(a, b, n, j + 1, k + 1, min, a[j]); // Левое поддерево

  
// Обёртка над isSameBSTUtil ()

static bool isSameBST(int []a, int []b, int n) 

    return isSameBSTUtil(a, b, n, 0, 0, 

                    int.MinValue,int.MaxValue); 

  
// Код драйвера

public static void Main(String[] args) 

    int []a = {8, 3, 6, 1, 4, 7, 10, 14, 13}; 

    int []b = {8, 10, 14, 3, 6, 4, 1, 7, 13}; 

    int n=a.Length; 

    Console.WriteLine("{0}\n", isSameBST(a, b, n)? 

                "BSTs are same":"BSTs not same"); 


  
// Этот код предоставлен 29AjayKumar

Выход:

BSTs are same

Эта статья составлена Амитом Джайном . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проверьте идентичные BST без построения деревьев

0.00 (0%) 0 votes