Algorithm
Problem Nmae: 95. Unique Binary Search Trees II
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]]
Constraints:
1 <= n <= 8
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if(n == 0) return {};
return DFS(1, n);
}
vector < TreeNode*> DFS(int l, int r){
vector<TreeNode*>res;
if(l > r) return {NULL};
for(int i = l; i <= r; i++){
auto left = DFS(l, i - 1);
auto right = DFS(i + 1, r);
for(auto x: left)
for(auto y: right){
TreeNode* root = new TreeNode(i>;
root->left = x;
root->right = y;
res.push_back(root);
}
}
return res;
}
};
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]]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const generateTrees = function(n) {
if (n === 0) return []
return genTreeList(1, n)
}
function genTreeList(start, end) {
const list = []
if (start > end) list.push(null)
for (let idx = start; idx < = end; idx++) {
const leftList = genTreeList(start, idx - 1)
const rightList = genTreeList(idx + 1, end)
for (let left of leftList) {
for (let right of rightList) {
const root = new TreeNode(idx)
root.left = left
root.right = right
list.push(root)
}
}
}
return list
}
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]]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def dfs(l, r):
if r < l: return [None]
arr = []
for m in range(l, r + 1):
left = dfs(l, m - 1)
right = dfs(m + 1, r)
for lNode in left:
for rNode in right:
new = TreeNode(m)
new.left = lNode
new.right = rNode
arr.append(new)
return arr
res = dfs(1, n)
return [] if res == [None] else res
Input
n = 1
Output
[[1]]
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _095_UniqueBinarySearchTree2
{
public IList < TreeNode> GenerateTrees(int n)
{
if (n == 0) return new List();
return GenerateTrees(1, n);
}
public IList < TreeNode> GenerateTrees(int start, int end)
{
List trees = new List();
if (start > end)
{
trees.Add(null);
return trees;
}
for (int i = start; i < = end; i++)
{
var leftTrees = GenerateTrees(start, i - 1);
var rightTrees = GenerateTrees(i + 1, end);
foreach (var leftTree in leftTrees)
foreach (var rightTree in rightTrees)
{
var current = new TreeNode(i);
current.left = leftTree;
current.right = rightTree;
trees.Add(current);
}
}
return trees;
}
}
}
Input
n = 1
Output
[[1]]