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.
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:
Solutions
Solution 1: DFS (Depth-First Search)
We design a function dfs(i, j) that returns all feasible binary search trees composed of [i, j], so the answer is dfs(1, n).
The execution steps of the function dfs(i, j) are as follows:
- If i > j, it means that there are no numbers to form a binary search tree at this time, so return a list consisting of a null node.
- If i ≤ j, we enumerate the numbers v in [i, j] as the root node. The left subtree of the root node v is composed of [i, v - 1], and the right subtree is composed of [v + 1, j]. Finally, we take the Cartesian product of all combinations of the left and right subtrees, i.e., left × right, add the root node v, and get all binary search trees with v as the root node.
The time complexity is O(n × G(n)), and the space complexity is O(n × G(n)). Where G(n) is the Catalan number.
PythonJavaC++GoTypeScriptRust
# 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]]:
def dfs(i: int, j: int) -> List[Optional[TreeNode]]:
if i > j:
return [None]
ans = []
for v in range(i, j + 1):
left = dfs(i, v - 1)
right = dfs(v + 1, j)
for l in left:
for r in right:
ans.append(TreeNode(v, l, r))
return ans
return dfs(1, n)(code-box)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
return dfs(1, n);
}
private List<TreeNode> dfs(int i, int j) {
List<TreeNode> ans = new ArrayList<>();
if (i > j) {
ans.add(null);
return ans;
}
for (int v = i; v <= j; ++v) {
var left = dfs(i, v - 1);
var right = dfs(v + 1, j);
for (var l : left) {
for (var r : right) {
ans.add(new TreeNode(v, l, r));
}
}
}
return ans;
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
function<vector<TreeNode*>(int, int)> dfs = [&](int i, int j) {
if (i > j) {
return vector<TreeNode*>{nullptr};
}
vector<TreeNode*> ans;
for (int v = i; v <= j; ++v) {
auto left = dfs(i, v - 1);
auto right = dfs(v + 1, j);
for (auto l : left) {
for (auto r : right) {
ans.push_back(new TreeNode(v, l, r));
}
}
}
return ans;
};
return dfs(1, n);
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func generateTrees(n int) []*TreeNode {
var dfs func(int, int) []*TreeNode
dfs = func(i, j int) []*TreeNode {
if i > j {
return []*TreeNode{nil}
}
ans := []*TreeNode{}
for v := i; v <= j; v++ {
left := dfs(i, v-1)
right := dfs(v+1, j)
for _, l := range left {
for _, r := range right {
ans = append(ans, &TreeNode{v, l, r})
}
}
}
return ans
}
return dfs(1, n)
}(code-box)
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function generateTrees(n: number): Array<TreeNode | null> {
const dfs = (i: number, j: number): Array<TreeNode | null> => {
if (i > j) {
return [null];
}
const ans: Array<TreeNode | null> = [];
for (let v = i; v <= j; ++v) {
const left = dfs(i, v - 1);
const right = dfs(v + 1, j);
for (const l of left) {
for (const r of right) {
ans.push(new TreeNode(v, l, r));
}
}
}
return ans;
};
return dfs(1, n);
}(code-box)
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
Self::dfs(1, n)
}
fn dfs(i: i32, j: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
let mut ans = Vec::new();
if i > j {
ans.push(None);
return ans;
}
for v in i..=j {
let left = Self::dfs(i, v - 1);
let right = Self::dfs(v + 1, j);
for l in &left {
for r in &right {
ans.push(Some(Rc::new(RefCell::new(TreeNode {
val: v,
left: l.clone(),
right: r.clone(),
}))));
}
}
}
ans
}
}(code-box)
