Leetcode Unique Binary Search Trees II problem solution

In this Leetcode Unique Binary Search Trees II problem solution we have Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Problem solution in Python.

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        
        if n<1:
            return []
        
        lst, dict_lst=[i+1 for i in range(n)], {tuple([]):[None]}
        
        def helper(lst):
            if tuple(lst) in dict_lst:
                return dict_lst[tuple(lst)] # need to be None for it to be used
            
            temp_tree=[]
            for i in range(len(lst)):
                left, right=lst[:i], lst[i+1:] 
                left_tree= helper(left)
                right_tree=helper(right)
                for x in left_tree:
                    for y in right_tree:
                        tree=TreeNode(lst[i])
                        tree.left=x
                        tree.right=y
                        temp_tree.append(tree)
                        
            dict_lst[tuple(lst)]=temp_tree
            return temp_tree
        
        return helper(lst)

Problem solution in Java.

class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[][] dp = new List[n][n];
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = i+1;
        }
        if(n == 0){
            return new ArrayList<>();
        }
        for(int i = n-1; i >= 0; i--){
            for(int j = i; j < n; j++){
                dp[i][j] = new ArrayList<>();
                List<TreeNode> one = new ArrayList<>();
                one.add(null);
                if(j == i){
                    TreeNode root = new TreeNode(nums[i]);
                    dp[i][j].add(root);
                    continue;
                }
                for(int k = i; k <= j; k++){
                    List<TreeNode> left = k==i ? one : dp[i][k-1];
                    List<TreeNode> right = k==j ? one : dp[k+1][j];
                    for(TreeNode l : left){
                        for(TreeNode r : right){
                            TreeNode root = new TreeNode(nums[k]);
                            root.left = l;
                            root.right = r;
                            dp[i][j].add(root);
                        }
                    }
                }
            }
        }
        return dp[0][n-1];
    }
}

Problem solution in C++.

map<int,vector<TreeNode*>> mp;
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n==0)
            return {};
     return cal(1,n);   
    }
    vector<TreeNode*> cal(int start,int end)
    {
        if(!mp[start*10+end].empty())
            return mp[start*10+end];
        if(start>end)
            return {NULL};
                      vector<TreeNode*> v;
        for(int i=start;i<=end;i++)
        {
            vector<TreeNode*> left=cal(start,i-1);
            vector<TreeNode*> right=cal(i+1,end);
            for(TreeNode * l:left)
            {
                for(TreeNode *r:right)
                {
                    TreeNode *current=new TreeNode(i);
                    current->left=l;
                    current->right=r;
                    v.push_back(current);
                }
            }
        }mp[start*10+end]=v;
        return v;
    }
};

Problem solution in C.

struct TreeNode** helper(int start,int end, int* returnSize){
    if(end<start){
        *returnSize=1;
        struct TreeNode** ret = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        ret[0]=NULL;
        return ret;
    }
    struct TreeNode** ret = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    *returnSize=0;
    for(int i=start;i<=end;i++){
        int leftReturnSize=0;
        int rightReturnSize=0;
        struct TreeNode** leftRet=helper(start,i-1,&leftReturnSize);
        struct TreeNode** rightRet=helper(i+1,end,&rightReturnSize);
        ret = realloc(ret,(leftReturnSize*rightReturnSize+*returnSize)*sizeof(struct TreeNode*));
        for(int left=0;left<leftReturnSize;left++){
            for(int right=0;right<rightReturnSize;right++){
                ret[(*returnSize)++]=(struct TreeNode*)malloc(sizeof(struct TreeNode));
                ret[(*returnSize)-1]->val=i;
                ret[(*returnSize)-1]->left=leftRet[left];
                ret[(*returnSize)-1]->right=rightRet[right];
            }
        }
    }
    return ret;
}
struct TreeNode** generateTrees(int n, int* returnSize){
    if(n==1){
        struct TreeNode** ret = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        *returnSize=1;
        ret[0]=(struct TreeNode*)malloc(sizeof(struct TreeNode));
        ret[0]->val=1;
        ret[0]->left=NULL;
        ret[0]->right=NULL;
    }
    if(n==0){
        *returnSize=0;
        return NULL;
    }
    return helper(1,n, returnSize);
}