Header Ad

Leetcode Unique Binary Search Trees problem solution

In this Leetcode Unique Binary Search Trees problem solution we have 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.

Leetcode Unique Binary Search Trees problem solution


Problem solution in Python.

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0 or n==1:
            return 1
        
        dp = [0]*(n+1)
        dp[0] = 1
        dp[1] = 1
        
        
        for i in range(2, n+1):
            for j in range(i):
                dp[i]+=dp[i-j-1] * dp[j]
                
        return dp[n]



Problem solution in Java.

public class Solution {
    public int numTrees(int n) {
        int[] record = new int[n+1];
        record[0] = 1;
        record[1] = 1;
        return numTrees(n, record);
    }
    
    public int numTrees(int n, int[] record) {
        int result = 0;
        for(int i=1; i<=n; i++) {
            int tmp = 1;
            int left = i - 1;
            int right = n - i;
            if(record[left] > 0) {
                tmp *= record[left];
            } else {
                tmp *= numTrees(left, record);
            }
            if(record[right] > 0) {
                tmp *= record[right];
            } else {
                tmp *= numTrees(right, record);
            }
            result += tmp;
        }
        record[n] = result;
        return result;
    }
}


Problem solution in C++.

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i-j-1];
            }
        }
        return dp[n];
    }
};


Problem solution in C.

int solutions[1024]={1,1,};
int calculated = 1;
int numTrees(int n) {
    if(n<calculated)
        return solutions[n];
    int start = calculated+1;
    for(int loop = start;loop<n+1;loop++){
        int sum = 0;
        for(int i=0;i<loop;i++){
            sum += solutions[i]*solutions[loop-i-1];
        }
        solutions[loop]=sum;
    }
    calculated = n;
    return solutions[n];
}


Post a Comment

0 Comments