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); }