Algorithm
Problem Nmae: 96. Unique Binary Search Trees
problem Link: https://leetcode.com/problems/unique-binary-search-trees/
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example 1:
Input: n = 3 Output: 5
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 19
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int numTrees(int n) {
int *dp;
int i, j;
dp = calloc((n + 1), sizeof(int));
//assert(dp);
dp[0] = dp[1] = 1;
for (i = 2; i < = n; i ++) {
for (j = 1; j < = i; j ++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
i = dp[n];
free(dp);
return i;
}
Input
n = 3
Output
5
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < = n; i++) {
for (int j = 1; j < = i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
Input
n = 3
Output
5
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const numTrees = function(n) {
const arr = new Array(n + 1).fill(0)
arr[0] = arr[1] = 1
for (let i = 2; i < = n; i++) {
for (let j = 1; j < = i; j++) {
arr[i] += arr[j - 1] * arr[i - j]
}
}
return arr[n]
}
Input
n = 1
Output
1
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numTrees(self, n):
if n <= 1:
return 1
catalan = [0] * (n + 1)
catalan[0] = catalan[1] = 1
for i in range(2, n + 1):
for j in range(i):
catalan[i] += catalan[j] * catalan[i - j - 1]
return catalan[n]
Input
n = 1
Output
1
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _096_UniqueBinarySearchTree
{
public int NumTrees(int n)
{
long result = 1;
for (int i = 0; i < n; i++)
result = result * 2 * (2 * i + 1) / (i + 2);
return (int)result;
}
}
}
Input
n = 3
Output
5