Dados dos números enteros N y H , la tarea es encontrar el recuento de distintos árboles binarios de búsqueda que consisten en N Nodes donde la profundidad o altura máxima del árbol es igual a H .
Nota: La altura de BST con solo el Node raíz es 0 .
Ejemplos:
Entrada: N = 2, H = 1
Salida: 2
Explicación: Los dos BST son:
BST’s de altura H = 1 y Nodes N = 2
Entrada: N = 3, H = 2
Salida: 4
Explicación: Los cuatro BST son:
BST’s de altura H = 2 y Nodes N = 3
Enfoque ingenuo: el problema se puede resolver utilizando recursividad , que se puede memorizar para obtener una solución de programación dinámica basada en la siguiente idea:
El problema se puede resolver de manera eficiente al encontrar el recuento de BST que tienen una profundidad máxima hasta H (es decir, [0 – H] ) en lugar de exactamente H.
Sea f(N, H) la cuenta de BST que consta de ‘N’ Nodes y tiene una profundidad máxima hasta ‘H’. Entonces, la solución para el problema anterior: el recuento de BST con una profundidad máxima de exactamente ‘H’ es igual a f(N, H) – f(N, H – 1) .
Siga la ilustración a continuación para una mejor comprensión.
Ilustración:
Considere: N = 3 , H = 2
La respuesta para este ejemplo es: recuento de BST de profundidad máxima hasta 2 – recuento de BST de profundidad máxima hasta 1 .
- El recuento de BST de profundidad máxima hasta 2 es 5 , son:
5 – BST de profundidad máxima hasta 2
- El recuento de BST de profundidad máxima hasta 1 es 1 , es:
1 – BST de profundidad máxima hasta 1
- Por lo tanto, el recuento de BST de profundidad máxima igual a ‘2’ es 4.
Siga los pasos que se mencionan a continuación para resolver el problema.
- La cuenta de BST con el Node i como Node raíz es igual al producto de la cuenta de BST del subárbol izquierdo formado por los Nodes 1 a i-1 y el subárbol derecho formado por los Nodes i +1 a N.
- Para encontrar el recuento de BST del subárbol izquierdo, podemos llamar recursivamente a la misma función para la profundidad H-1 y N=i – 1 . Para encontrar el recuento de BST del subárbol derecho, llame recursivamente a la función para la profundidad H-1 y N=Ni .
- Recorra todos los valores de i de [1, N] como Node raíz y agregue el producto de la cuenta del subárbol izquierdo y derecho al resultado.
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la programación dinámica porque el problema anterior tiene subproblemas superpuestos y una subestructura óptima . Los subproblemas se pueden almacenar en la memorización de la tabla dp[][] donde dp[N][H] almacena el recuento de BST de profundidad máxima hasta H que consta de N Nodes. Siga los pasos a continuación para resolver el problema:
- Inicialice una array multidimensional global dp[105][105] con todos los valores como -1 que almacena el resultado de cada llamada recursiva.
- Defina una función recursiva , diga countOfBST(N, H) y realice los siguientes pasos.
- Caso 1: Si N = 0 , devuelve 1 .
- Caso 2: si H = 0 , devuelve verdadero si N = 1 .
- Si el resultado del estado dp[N][H] ya se calculó, devuelva este valor dp[N][H] .
- Itere sobre el rango [1, N] usando la variable ‘ i ‘ como raíz y realice las siguientes operaciones.
- Multiplique el valor de las funciones recursivas countOfBST(i – 1, H – 1) y countOfBST(N – i, H – 1) . Las dos funciones calculan el conteo de BST para el subárbol izquierdo y derecho respectivamente.
- Agregue el término a la respuesta final que almacena el recuento total de BST posibles para todas las raíces de [1, N] .
- Imprime el valor devuelto por la función countOfBST(N, H) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Declaring a dp-array
int dp[105][105];
const int mod = 1000000007;
// Function to find the count of
// BST upto height 'H' consisting
// of 'N' nodes.
int countOfBST(int N, int H)
{
// Base Case1 : If N == 0, return
// 1 as a valid BST has been formed
if (N == 0) {
return 1;
}
// Base Case2 : If H == 0, return true
// if N == 1
if (H == 0) {
return N == 1;
}
// If the current state has already
// been computed, then return it.
if (dp[N][H] != -1) {
return dp[N][H];
}
// Initialize answer to 0.
int ans = 0;
// Iterate over all numbers from
// [1, N], with 'i' as root.
for (int i = 1; i <= N; ++i) {
// Call the recursive functions to
// find count of BST of left and right
// subtrees. Add the product of
// both terms to the answer.
ans += (countOfBST(i - 1, H - 1) * 1LL
* countOfBST(N - i, H - 1))
% mod;
// Take modulo 1000000007
ans %= mod;
}
// Return ans
return dp[N][H] = ans;
}
// Utility function to find the count
// of BST upto height 'H' consisting
// of 'N' nodes.
int UtilCountOfBST(int N, int H)
{
// Initialize dp-array with -1.
memset(dp, -1, sizeof dp);
// If height is 0, return true if
// only one node is present.
if (H == 0) {
return (N == 1);
}
// Function call.
return (countOfBST(N, H)
- countOfBST(N, H - 1)
+ mod)
% mod;
}
// Driver code
int main()
{
// Number of nodes
int N = 3;
// Height of tree
int H = 2;
cout << UtilCountOfBST(N, H) << endl;
return 0;
}
Java
// Java implementation of above approach
import java.io.*;
import java.util.*;
class GFG {
// Declaring a dp-array
static int[][] dp = new int[105][105];
static int mod = 1000000007;
// Function to find the count of
// BST upto height 'H' consisting
// of 'N' nodes.
static int countOfBST(int N, int H)
{
// Base Case1 : If N == 0, return
// 1 as a valid BST has been formed
if (N == 0) {
return 1;
}
// Base Case2 : If H == 0, return true
// if N == 1
if (H == 0) {
if (N == 1)
return 1;
return 0;
}
// If the current state has already
// been computed, then return it.
if (dp[N][H] != -1) {
return dp[N][H];
}
// Initialize answer to 0.
int ans = 0;
// Iterate over all numbers from
// [1, N], with 'i' as root.
for (int i = 1; i <= N; ++i) {
// Call the recursive functions to
// find count of BST of left and right
// subtrees. Add the product of
// both terms to the answer.
ans += (countOfBST(i - 1, H - 1)
* countOfBST(N - i, H - 1))
% mod;
// Take modulo 1000000007
ans %= mod;
}
// Return ans
dp[N][H] = ans;
return dp[N][H];
}
// Utility function to find the count
// of BST upto height 'H' consisting
// of 'N' nodes.
static int UtilCountOfBST(int N, int H)
{
// Initialize dp-array with -1.
for (int i = 0; i < 105; i++)
for (int j = 0; j < 105; j++)
dp[i][j] = -1;
// If height is 0, return true if
// only one node is present.
if (H == 0) {
if (N == 1)
return 1;
return 0;
}
// Function call.
return (countOfBST(N, H) - countOfBST(N, H - 1)
+ mod)
% mod;
}
// Driver Code
public static void main(String[] args)
{
// Number of nodes
int N = 3;
// Height of tree
int H = 2;
System.out.print(UtilCountOfBST(N, H));
}
}
// This code is contributed by code_hunt.
Python3
# python3 code to implement the approach # Declaring a dp-array dp = [[-1 for _ in range(105)] for _ in range(105)] mod = 1000000007 # Function to find the count of # BST upto height 'H' consisting # of 'N' nodes. def countOfBST(N, H): # Base Case1 : If N == 0, return # 1 as a valid BST has been formed if (N == 0): return 1 # Base Case2 : If H == 0, return true # if N == 1 if (H == 0): return N == 1 # If the current state has already # been computed, then return it. if (dp[N][H] != -1): return dp[N][H] # Initialize answer to 0. ans = 0 # Iterate over all numbers from # [1, N], with 'i' as root. for i in range(1, N+1): # Call the recursive functions to # find count of BST of left and right # subtrees. Add the product of # both terms to the answer. ans += (countOfBST(i - 1, H - 1) * countOfBST(N - i, H - 1)) % mod # Take modulo 1000000007 ans %= mod # Return ans dp[N][H] = ans return dp[N][H] # Utility function to find the count # of BST upto height 'H' consisting # of 'N' nodes. def UtilCountOfBST(N, H): # Initialize dp-array with -1. # If height is 0, return true if # only one node is present. if (H == 0): return (N == 1) # Function call. return (countOfBST(N, H) - countOfBST(N, H - 1) + mod) % mod # Driver code if __name__ == "__main__": # Number of nodes N = 3 # Height of tree H = 2 print(UtilCountOfBST(N, H)) # This code is contributed by rakeshsahni
C#
// C# code to implement the approach
using System;
class GFG {
// Declaring a dp-array
static int[, ] dp = new int[105, 105];
const int mod = 1000000007;
// Function to find the count of
// BST upto height 'H' consisting
// of 'N' nodes.
static int countOfBST(int N, int H)
{
// Base Case1 : If N == 0, return
// 1 as a valid BST has been formed
if (N == 0) {
return 1;
}
// Base Case2 : If H == 0, return true
// if N == 1
if (H == 0) {
if (N == 1)
return 1;
return 0;
}
// If the current state has already
// been computed, then return it.
if (dp[N, H] != -1) {
return dp[N, H];
}
// Initialize answer to 0.
int ans = 0;
// Iterate over all numbers from
// [1, N], with 'i' as root.
for (int i = 1; i <= N; ++i) {
// Call the recursive functions to
// find count of BST of left and right
// subtrees. Add the product of
// both terms to the answer.
ans += (countOfBST(i - 1, H - 1)
* countOfBST(N - i, H - 1))
% mod;
// Take modulo 1000000007
ans %= mod;
}
// Return ans
dp[N, H] = ans;
return dp[N, H];
}
// Utility function to find the count
// of BST upto height 'H' consisting
// of 'N' nodes.
static int UtilCountOfBST(int N, int H)
{
// Initialize dp-array with -1.
for (int i = 0; i < 105; i++)
for (int j = 0; j < 105; j++)
dp[i, j] = -1;
// If height is 0, return true if
// only one node is present.
if (H == 0) {
if (N == 1)
return 1;
return 0;
}
// Function call.
return (countOfBST(N, H) - countOfBST(N, H - 1)
+ mod)
% mod;
}
// Driver code
public static void Main()
{
// Number of nodes
int N = 3;
// Height of tree
int H = 2;
Console.Write(UtilCountOfBST(N, H));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Declaring a dp-array
let dp = new Array(105);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(105).fill(-1);
}
let mod = 1000000007;
// Function to find the count of
// BST upto height 'H' consisting
// of 'N' nodes.
function countOfBST(N, H) {
// Base Case1 : If N == 0, return
// 1 as a valid BST has been formed
if (N == 0) {
return 1;
}
// Base Case2 : If H == 0, return true
// if N == 1
if (H == 0) {
return N == 1;
}
// If the current state has already
// been computed, then return it.
if (dp[N][H] != -1) {
return dp[N][H];
}
// Initialize answer to 0.
let ans = 0;
// Iterate over all numbers from
// [1, N], with 'i' as root.
for (let i = 1; i <= N; ++i) {
// Call the recursive functions to
// find count of BST of left and right
// subtrees. Add the product of
// both terms to the answer.
ans += (countOfBST(i - 1, H - 1) * 1
* countOfBST(N - i, H - 1))
% mod;
// Take modulo 1000000007
ans %= mod;
}
// Return ans
return dp[N][H] = ans;
}
// Utility function to find the count
// of BST upto height 'H' consisting
// of 'N' nodes.
function UtilCountOfBST(N, H) {
// If height is 0, return true if
// only one node is present.
if (H == 0) {
return (N == 1);
}
// Function call.
return (countOfBST(N, H)
- countOfBST(N, H - 1)
+ mod)
% mod;
}
// Driver code
// Number of nodes
let N = 3;
// Height of tree
let H = 2;
document.write(UtilCountOfBST(N, H) + '<br>');
// This code is contributed by Potta Lokesh
</script>
Producción
4
Complejidad de Tiempo: O(N 2 * H) Espacio
Auxiliar : O(N * H)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA