Description:
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.
Examples:
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]]Solution in Python:
To solve the problem of generating all structurally unique BSTs (binary search trees) with n nodes, where the nodes have unique values from 1 to n, we can use a recursive approach. The idea is to consider each number from 1 to n as the root and then recursively construct all possible left and right subtrees.
Python
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
if n == 0:
return []
# Function to generate all BSTs with nodes from start to end
def generate_trees(start: int, end: int) -> List[Optional[TreeNode]]:
if start > end:
return [None]
all_trees = []
# Loop through each number as the root value
for i in range(start, end + 1):
# Generate all left and right subtrees
left_trees = generate_trees(start, i - 1)
right_trees = generate_trees(i + 1, end)
# Combine each left and right subtree with the root i
for left in left_trees:
for right in right_trees:
current_tree = TreeNode(i)
current_tree.left = left
current_tree.right = right
all_trees.append(current_tree)
return all_trees
return generate_trees(1, n)Detailed Comments on the Code:
- TreeNode Class:
- A simple definition for a binary tree node which includes a value (
val), a left child (left), and a right child (right).
- A simple definition for a binary tree node which includes a value (
- generateTrees Method:
- This is the main method that will be called to generate all unique BSTs with
nnodes. - If
nis 0, it returns an empty list as there are no BSTs possible.
- This is the main method that will be called to generate all unique BSTs with
- generate_trees Function:
- This helper function is used to generate all BSTs with values from
starttoend. - If
startis greater thanend, it returns a list containingNone, which represents an empty tree.
- This helper function is used to generate all BSTs with values from
- Loop through each number as the root:
- For each number
ifromstarttoend, the numberiis considered as the root of the BST. - Recursively generate all possible left subtrees with values less than
iand all possible right subtrees with values greater thani.
- For each number
- Combine left and right subtrees:
- For each combination of left and right subtrees, a new tree is created with
ias the root,leftas the left child, andrightas the right child. - This new tree is added to the list of all possible trees.
- For each combination of left and right subtrees, a new tree is created with
- Return all generated trees:
- Finally, the function returns the list of all possible BSTs for the given range.
By using this recursive approach, we can generate all structurally unique BSTs for a given n. Each tree is constructed by choosing each value as the root and recursively constructing the left and right subtrees.
Solution in Javascript:
JavaScript
/**
* @param {number} n
* @return {TreeNode[]}
*/
var generateTrees = function(n) {
if (n === 0) {
return [];
}
/**
* Function to generate all BSTs with nodes from start to end
* @param {number} start
* @param {number} end
* @return {TreeNode[]}
*/
function generateTreesInRange(start, end) {
if (start > end) {
return [null];
}
const allTrees = [];
// Loop through each number as the root value
for (let i = start; i <= end; i++) {
// Generate all left and right subtrees
const leftTrees = generateTreesInRange(start, i - 1);
const rightTrees = generateTreesInRange(i + 1, end);
// Combine each left and right subtree with the root i
for (const left of leftTrees) {
for (const right of rightTrees) {
const currentTree = new TreeNode(i);
currentTree.left = left;
currentTree.right = right;
allTrees.push(currentTree);
}
}
}
return allTrees;
}
return generateTreesInRange(1, n);
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new ArrayList<>();
}
return generateTreesInRange(1, n);
}
private List<TreeNode> generateTreesInRange(int start, int end) {
List<TreeNode> allTrees = new ArrayList<>();
if (start > end) {
allTrees.add(null); // Add null to represent an empty tree
return allTrees;
}
// Loop through each number as the root value
for (int i = start; i <= end; i++) {
// Generate all left and right subtrees
List<TreeNode> leftTrees = generateTreesInRange(start, i - 1);
List<TreeNode> rightTrees = generateTreesInRange(i + 1, end);
// Combine each left and right subtree with the root i
for (TreeNode left : leftTrees) {
for (TreeNode right : rightTrees) {
TreeNode currentTree = new TreeNode(i);
currentTree.left = left;
currentTree.right = right;
allTrees.add(currentTree);
}
}
}
return allTrees;
}
}Solution in C#:
C#
public class Solution {
public IList<TreeNode> GenerateTrees(int n) {
if (n == 0) {
return new List<TreeNode>();
}
return GenerateTrees(1, n);
}
private Dictionary<(int, int), IList<TreeNode>> memo = new Dictionary<(int, int), IList<TreeNode>>();
private IList<TreeNode> GenerateTrees(int start, int end) {
if (start > end) {
return new List<TreeNode> { null };
}
if (memo.ContainsKey((start, end))) {
return memo[(start, end)];
}
IList<TreeNode> result = new List<TreeNode>();
for (int i = start; i <= end; i++) {
IList<TreeNode> leftTrees = GenerateTrees(start, i - 1);
IList<TreeNode> rightTrees = GenerateTrees(i + 1, end);
foreach (var leftTree in leftTrees) {
foreach (var rightTree in rightTrees) {
TreeNode root = new TreeNode(i);
root.left = leftTree;
root.right = rightTree;
result.Add(root);
}
}
}
memo[(start, end)] = result;
return result;
}
}