Unique Binary Search Tree II Problem: 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.
Input: n = 3 Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Table of Contents
Unique Binary Search Tree II Problem Solution
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);
}