Dada una array , arr[] de tamaño N que consta de elementos del rango [1, N] , que representa el orden en que los elementos se insertan en un árbol de búsqueda binario , la tarea es contar el número de formas de reorganizar la array dada para obtener el mismo BST .
Ejemplos:
Entrada: arr[ ] ={3, 4, 5, 1, 2}
Salida: 6
Explicación:
las permutaciones de la array que representan el mismo BST son: {{3, 4, 5, 1, 2}, {3, 1, 2, 4, 5}, {3, 1, 4, 2, 5}, {3, 1, 4, 5, 2}, {3, 4, 1, 2, 5}, {3, 4, 1, 5, 2}}. Por lo tanto, la salida es 6.Entrada: arr[ ] ={2, 1, 6, 5, 4, 3}
Salida: 5
Enfoque: la idea es arreglar primero el Node raíz y luego contar recursivamente el número de formas de reorganizar los elementos del subárbol izquierdo y los elementos del subárbol derecho de tal manera que el orden relativo dentro de los elementos del subárbol izquierdo y el subárbol derecho debe ser el mismo. Aquí está la relación de recurrencia:
contarVías(arr) = contarVías(izquierda) * contarVías(derecha) * combinaciones(N, X).
izquierda: Contiene todos los elementos del subárbol izquierdo (Elementos que son menores que la raíz)
derecha: Contiene todos los elementos del subárbol derecho (Elementos que son mayores que la raíz)
N = Número total de elementos en arr[]
X = Número total de elementos en el subárbol izquierdo.
Siga los pasos a continuación para resolver el problema:
- Repare el Node raíz de BST y almacene los elementos del subárbol izquierdo (Elementos que son menores que arr[0]), diga ctLeft[] y almacene los elementos del subárbol derecho (Elementos que son mayores que arr[0] ), diga ctRight[].
- Para generar BST idénticos, mantenga el orden relativo dentro de los elementos del subárbol izquierdo y el subárbol derecho.
- Calcule la cantidad de formas de reorganizar la array para generar BST utilizando la relación de recurrencia mencionada anteriormente.
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to precompute the // factorial of 1 to N void calculateFact(int fact[], int N) { fact[0] = 1; for (long long int i = 1; i < N; i++) { fact[i] = fact[i - 1] * i; } } // Function to get the value of nCr int nCr(int fact[], int N, int R) { if (R > N) return 0; // nCr= fact(n)/(fact(r)*fact(n-r)) int res = fact[N] / fact[R]; res /= fact[N - R]; return res; } // Function to count the number of ways // to rearrange the array to obtain same BST int countWays(vector<int>& arr, int fact[]) { // Store the size of the array int N = arr.size(); // Base case if (N <= 2) { return 1; } // Store the elements of the // left subtree of BST vector<int> leftSubTree; // Store the elements of the // right subtree of BST vector<int> rightSubTree; // Store the root node int root = arr[0]; for (int i = 1; i < N; i++) { // Push all the elements // of the left subtree if (arr[i] < root) { leftSubTree.push_back( arr[i]); } // Push all the elements // of the right subtree else { rightSubTree.push_back( arr[i]); } } // Store the size of leftSubTree int N1 = leftSubTree.size(); // Store the size of rightSubTree int N2 = rightSubTree.size(); // Recurrence relation int countLeft = countWays(leftSubTree, fact); int countRight = countWays(rightSubTree, fact); return nCr(fact, N - 1, N1) * countLeft * countRight; } // Driver Code int main() { vector<int> arr; arr = { 3, 4, 5, 1, 2 }; // Store the size of arr int N = arr.size(); // Store the factorial up to N int fact[N]; // Precompute the factorial up to N calculateFact(fact, N); cout << countWays(arr, fact); return 0; }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to precompute the // factorial of 1 to N static void calculateFact(int fact[], int N) { fact[0] = 1; for(int i = 1; i < N; i++) { fact[i] = fact[i - 1] * i; } } // Function to get the value of nCr static int nCr(int fact[], int N, int R) { if (R > N) return 0; // nCr= fact(n)/(fact(r)*fact(n-r)) int res = fact[N] / fact[R]; res /= fact[N - R]; return res; } // Function to count the number of ways // to rearrange the array to obtain same BST static int countWays(Vector<Integer> arr, int fact[]) { // Store the size of the array int N = arr.size(); // Base case if (N <= 2) { return 1; } // Store the elements of the // left subtree of BST Vector<Integer> leftSubTree = new Vector<Integer>(); // Store the elements of the // right subtree of BST Vector<Integer> rightSubTree = new Vector<Integer>(); // Store the root node int root = arr.get(0); for(int i = 1; i < N; i++) { // Push all the elements // of the left subtree if (arr.get(i) < root) { leftSubTree.add(arr.get(i)); } // Push all the elements // of the right subtree else { rightSubTree.add(arr.get(i)); } } // Store the size of leftSubTree int N1 = leftSubTree.size(); // Store the size of rightSubTree int N2 = rightSubTree.size(); // Recurrence relation int countLeft = countWays(leftSubTree, fact); int countRight = countWays(rightSubTree, fact); return nCr(fact, N - 1, N1) * countLeft * countRight; } // Driver Code public static void main(String[] args) { int []a = { 3, 4, 5, 1, 2 }; Vector<Integer> arr = new Vector<Integer>(); for(int i : a) arr.add(i); // Store the size of arr int N = a.length; // Store the factorial up to N int []fact = new int[N]; // Precompute the factorial up to N calculateFact(fact, N); System.out.print(countWays(arr, fact)); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program to implement # the above approach # Function to precompute the # factorial of 1 to N def calculateFact(fact: list, N: int) -> None: fact[0] = 1 for i in range(1, N): fact[i] = fact[i - 1] * i # Function to get the value of nCr def nCr(fact: list, N: int, R: int) -> int: if (R > N): return 0 # nCr= fact(n)/(fact(r)*fact(n-r)) res = fact[N] // fact[R] res //= fact[N - R] return res # Function to count the number of ways # to rearrange the array to obtain same BST def countWays(arr: list, fact: list) -> int: # Store the size of the array N = len(arr) # Base case if (N <= 2): return 1 # Store the elements of the # left subtree of BST leftSubTree = [] # Store the elements of the # right subtree of BST rightSubTree = [] # Store the root node root = arr[0] for i in range(1, N): # Push all the elements # of the left subtree if (arr[i] < root): leftSubTree.append(arr[i]) # Push all the elements # of the right subtree else: rightSubTree.append(arr[i]) # Store the size of leftSubTree N1 = len(leftSubTree) # Store the size of rightSubTree N2 = len(rightSubTree) # Recurrence relation countLeft = countWays(leftSubTree, fact) countRight = countWays(rightSubTree, fact) return (nCr(fact, N - 1, N1) * countLeft * countRight) # Driver Code if __name__ == '__main__': arr = [ 3, 4, 5, 1, 2 ] # Store the size of arr N = len(arr) # Store the factorial up to N fact = [0] * N # Precompute the factorial up to N calculateFact(fact, N) print(countWays(arr, fact)) # This code is contributed by sanjeev2552
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to precompute the // factorial of 1 to N static void calculateFact(int []fact, int N) { fact[0] = 1; for(int i = 1; i < N; i++) { fact[i] = fact[i - 1] * i; } } // Function to get the value of nCr static int nCr(int []fact, int N, int R) { if (R > N) return 0; // nCr= fact(n)/(fact(r)*fact(n-r)) int res = fact[N] / fact[R]; res /= fact[N - R]; return res; } // Function to count the number of ways // to rearrange the array to obtain same BST static int countWays(List<int> arr, int []fact) { // Store the size of the array int N = arr.Count; // Base case if (N <= 2) { return 1; } // Store the elements of the // left subtree of BST List<int> leftSubTree = new List<int>(); // Store the elements of the // right subtree of BST List<int> rightSubTree = new List<int>(); // Store the root node int root = arr[0]; for(int i = 1; i < N; i++) { // Push all the elements // of the left subtree if (arr[i] < root) { leftSubTree.Add(arr[i]); } // Push all the elements // of the right subtree else { rightSubTree.Add(arr[i]); } } // Store the size of leftSubTree int N1 = leftSubTree.Count; // Store the size of rightSubTree int N2 = rightSubTree.Count; // Recurrence relation int countLeft = countWays(leftSubTree, fact); int countRight = countWays(rightSubTree, fact); return nCr(fact, N - 1, N1) * countLeft * countRight; } // Driver Code public static void Main(String[] args) { int []a = { 3, 4, 5, 1, 2 }; List<int> arr = new List<int>(); foreach(int i in a) arr.Add(i); // Store the size of arr int N = a.Length; // Store the factorial up to N int []fact = new int[N]; // Precompute the factorial up to N calculateFact(fact, N); Console.Write(countWays(arr, fact)); } } // This code is contributed by Amit Katiyar
Javascript
<script> // JavaScript program to implement // the above approach // Function to precompute the // factorial of 1 to N function calculateFact(fact, N) { fact[0] = 1; for (var i = 1; i < N; i++) { fact[i] = fact[i - 1] * i; } } // Function to get the value of nCr function nCr(fact, N, R) { if (R > N) return 0; // nCr= fact(n)/(fact(r)*fact(n-r)) var res = parseInt(fact[N] / fact[R]); res = parseInt(res / fact[N - R]); return res; } // Function to count the number of ways // to rearrange the array to obtain same BST function countWays(arr, fact) { // Store the size of the array var N = arr.length; // Base case if (N <= 2) { return 1; } // Store the elements of the // left subtree of BST var leftSubTree = []; // Store the elements of the // right subtree of BST var rightSubTree = []; // Store the root node var root = arr[0]; for (var i = 1; i < N; i++) { // Push all the elements // of the left subtree if (arr[i] < root) { leftSubTree.push( arr[i]); } // Push all the elements // of the right subtree else { rightSubTree.push( arr[i]); } } // Store the size of leftSubTree var N1 = leftSubTree.length; // Store the size of rightSubTree var N2 = rightSubTree.length; // Recurrence relation var countLeft = countWays(leftSubTree, fact); var countRight = countWays(rightSubTree, fact); return nCr(fact, N - 1, N1) * countLeft * countRight; } // Driver Code var arr = []; arr = [3, 4, 5, 1, 2]; // Store the size of arr var N = arr.length; // Store the factorial up to N var fact = Array(N); // Precompute the factorial up to N calculateFact(fact, N); document.write( countWays(arr, fact)); </script>
6
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA