Here, We see Unique Binary Search Trees II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python etc. with different approaches.
List of all LeetCode Solution
![Unique Binary Search Trees II LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Unique Binary Search Trees II LeetCode Solution
Table of Contents
Problem Statement
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.
Example 1: 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]] Example 2: Input: n = 1 Output: [[1]]
Unique Binary Search Trees II Leetcode Solution C++
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if(n == 0) return vector<TreeNode *>(1, NULL);
vector<vector<vector<TreeNode*>>> subtree(n+2, vector<vector<TreeNode*>>(n+2, vector<TreeNode*>()));
for(int i=1; i<=n+1; ++i){
subtree[i][i].push_back(new TreeNode(i));
subtree[i][i-1].push_back(NULL);
}
for(int l=2; l<=n; ++l){
for(int i=1; i<=n-l+1; ++i){
for(int j=i; j<=i+l-1; ++j){
for(int k=0; k<subtree[j+1][i+l-1].size(); ++k){
for(int m=0; m<subtree[i][j-1].size(); ++m){
TreeNode *T = new TreeNode(j);
T->left = subtree[i][j-1][m];
T->right = subtree[j+1][i+l-1][k];
subtree[i][i+l-1].push_back(T);
}
}
}
}
}
return subtree[1][n];
}
};
Code language: PHP (php)
Unique Binary Search Trees II Leetcode Solution Java
class Solution {
public List<TreeNode> generateTrees(int n) {
return generateTrees(1,n);
}
public List<TreeNode> generateTrees(int start,int end){
List<TreeNode> trees = new ArrayList<TreeNode>();
if(start>end){ trees.add(null); return trees;}
for(int rootValue=start;rootValue<=end;rootValue++){
List<TreeNode> leftSubTrees=generateTrees(start,rootValue-1);
List<TreeNode> rightSubTrees=generateTrees(rootValue+1,end);
for(TreeNode leftSubTree:leftSubTrees){
for(TreeNode rightSubTree:rightSubTrees){
TreeNode root=new TreeNode(rootValue);
root.left=leftSubTree;
root.right=rightSubTree;
trees.add(root);
}
}
}
return trees;
}
}
Code language: PHP (php)
Unique Binary Search Trees II Leetcode Solution JavaScript
var generateTrees = function(n) {
const constructArray = (start, end) => {
const result = [];
if(start > end){
return [null];
}
if(start===end){
return [new TreeNode(start)];
}
if(end-start===1){
const first = new TreeNode(start, null, new TreeNode(end));
const second = new TreeNode(end, new TreeNode(start), null);
return [first, second];
}
for(let i=start; i<=end; i++){
const leftSide = constructArray(start, i-1);
const rightSide = constructArray(i+1, end);
leftSide.forEach(ls => {
rightSide.forEach(rs => {
const tree = new TreeNode(i, ls, rs);
result.push(tree);
})
})
}
return result;
}
return constructArray(1,n);
};
Code language: JavaScript (javascript)
Unique Binary Search Trees II Leetcode Solution Python
class Solution(object):
def generateTrees(self, n):
def node(val, left, right):
node = TreeNode(val)
node.left = left
node.right = right
return node
def trees(first, last):
return [node(root, left, right)
for root in range(first, last+1)
for left in trees(first, root-1)
for right in trees(root+1, last)] or [None]
return trees(1, n)