LeetCode 95: Unique Binary Search Trees II (Recursive Interval Construction)
LeetCode 95TreeRecursionToday we solve LeetCode 95 - Unique Binary Search Trees II.
Source: https://leetcode.com/problems/unique-binary-search-trees-ii/
English
Problem Summary
Given an integer n, return all structurally unique BSTs storing values from 1..n.
Key Insight
For interval [l, r], if root is k, then left subtree must come from [l, k-1] and right subtree from [k+1, r]. For each root candidate, the result is all combinations from left-list × right-list.
Optimal Algorithm (Step-by-Step)
1) Define build(l, r) to generate all BST roots from interval [l, r].
2) Base case: if l > r, return list [null] as one valid empty subtree choice.
3) Enumerate root value k from l to r.
4) Recursively compute all left trees and right trees.
5) Combine every left with every right under a newly created root k.
6) Memoize by (l, r) to avoid repeated interval expansion.
Complexity Analysis
Let Cn be the nth Catalan number (count of unique BSTs).
Time: O(n * Cn) for constructing all nodes over all results.
Space: O(n * Cn) including output plus recursion/memoization.
Common Pitfalls
- Not returning null for empty intervals, which breaks combinations.
- Reusing one root object across pairs instead of allocating a new root each time.
- Missing memoization and causing heavy repeated recursion.
- Off-by-one errors in [l, k-1] and [k+1, r].
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private Map> memo = new HashMap<>();
public List generateTrees(int n) {
if (n == 0) return new ArrayList<>();
return build(1, n);
}
private List build(int l, int r) {
String key = l + "," + r;
if (memo.containsKey(key)) return memo.get(key);
List res = new ArrayList<>();
if (l > r) {
res.add(null);
memo.put(key, res);
return res;
}
for (int k = l; k <= r; k++) {
List left = build(l, k - 1);
List right = build(k + 1, r);
for (TreeNode a : left) {
for (TreeNode b : right) {
TreeNode root = new TreeNode(k);
root.left = a;
root.right = b;
res.add(root);
}
}
}
memo.put(key, res);
return res;
}
} func generateTrees(n int) []*TreeNode {
if n == 0 {
return []*TreeNode{}
}
memo := map[[2]int][]*TreeNode{}
var build func(l, r int) []*TreeNode
build = func(l, r int) []*TreeNode {
key := [2]int{l, r}
if v, ok := memo[key]; ok {
return v
}
if l > r {
return []*TreeNode{nil}
}
res := []*TreeNode{}
for k := l; k <= r; k++ {
left := build(l, k-1)
right := build(k+1, r)
for _, a := range left {
for _, b := range right {
root := &TreeNode{Val: k}
root.Left = a
root.Right = b
res = append(res, root)
}
}
}
memo[key] = res
return res
}
return build(1, n)
}class Solution {
public:
vector generateTrees(int n) {
if (n == 0) return {};
return build(1, n);
}
private:
unordered_map> memo;
vector build(int l, int r) {
long long key = (static_cast(l) << 32) | static_cast(r);
if (memo.count(key)) return memo[key];
vector res;
if (l > r) {
res.push_back(nullptr);
return memo[key] = res;
}
for (int k = l; k <= r; ++k) {
auto left = build(l, k - 1);
auto right = build(k + 1, r);
for (auto a : left) {
for (auto b : right) {
TreeNode* root = new TreeNode(k);
root->left = a;
root->right = b;
res.push_back(root);
}
}
}
return memo[key] = res;
}
}; class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
if n == 0:
return []
from functools import lru_cache
@lru_cache(None)
def build(l: int, r: int):
if l > r:
return (None,)
res = []
for k in range(l, r + 1):
left = build(l, k - 1)
right = build(k + 1, r)
for a in left:
for b in right:
root = TreeNode(k)
root.left = a
root.right = b
res.append(root)
return tuple(res)
return list(build(1, n))var generateTrees = function(n) {
if (n === 0) return [];
const memo = new Map();
const build = (l, r) => {
const key = `${l},${r}`;
if (memo.has(key)) return memo.get(key);
const res = [];
if (l > r) {
res.push(null);
memo.set(key, res);
return res;
}
for (let k = l; k <= r; k++) {
const left = build(l, k - 1);
const right = build(k + 1, r);
for (const a of left) {
for (const b of right) {
const root = new TreeNode(k);
root.left = a;
root.right = b;
res.push(root);
}
}
}
memo.set(key, res);
return res;
};
return build(1, n);
};中文
题目概述
给定整数 n，返回所有由 1..n 构成且结构互不相同的二叉搜索树。
核心思路
在区间 [l, r] 内，若根节点取 k，则左子树只能来自 [l, k-1]，右子树只能来自 [k+1, r]。每个根的结果就是左右候选集合的笛卡尔积组合。
最优算法（步骤）
1）定义 build(l, r)，返回区间内所有合法 BST 根节点集合。
2）若 l > r，返回 [null]，表示空子树也是一种可组合情况。
3）枚举根节点值 k。
4）递归得到左集合和右集合。
5）双层循环组合左右子树，每一对都新建一个值为 k 的根。
6）按区间 (l, r) 记忆化，避免重复展开。
复杂度分析
设 Cn 为第 n 个 Catalan 数（也是答案数量级）。
时间复杂度：O(n * Cn)。
空间复杂度：O(n * Cn)（含结果、递归栈与缓存）。
常见陷阱
- 空区间没有返回 null，会漏解。
- 组合时复用根对象导致多棵树互相污染。
- 不做记忆化导致性能显著下降。
- 区间边界写错（k-1/k+1）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private Map> memo = new HashMap<>();
public List generateTrees(int n) {
if (n == 0) return new ArrayList<>();
return build(1, n);
}
private List build(int l, int r) {
String key = l + "," + r;
if (memo.containsKey(key)) return memo.get(key);
List res = new ArrayList<>();
if (l > r) {
res.add(null);
memo.put(key, res);
return res;
}
for (int k = l; k <= r; k++) {
List left = build(l, k - 1);
List right = build(k + 1, r);
for (TreeNode a : left) {
for (TreeNode b : right) {
TreeNode root = new TreeNode(k);
root.left = a;
root.right = b;
res.add(root);
}
}
}
memo.put(key, res);
return res;
}
} func generateTrees(n int) []*TreeNode {
if n == 0 {
return []*TreeNode{}
}
memo := map[[2]int][]*TreeNode{}
var build func(l, r int) []*TreeNode
build = func(l, r int) []*TreeNode {
key := [2]int{l, r}
if v, ok := memo[key]; ok {
return v
}
if l > r {
return []*TreeNode{nil}
}
res := []*TreeNode{}
for k := l; k <= r; k++ {
left := build(l, k-1)
right := build(k+1, r)
for _, a := range left {
for _, b := range right {
root := &TreeNode{Val: k}
root.Left = a
root.Right = b
res = append(res, root)
}
}
}
memo[key] = res
return res
}
return build(1, n)
}class Solution {
public:
vector generateTrees(int n) {
if (n == 0) return {};
return build(1, n);
}
private:
unordered_map> memo;
vector build(int l, int r) {
long long key = (static_cast(l) << 32) | static_cast(r);
if (memo.count(key)) return memo[key];
vector res;
if (l > r) {
res.push_back(nullptr);
return memo[key] = res;
}
for (int k = l; k <= r; ++k) {
auto left = build(l, k - 1);
auto right = build(k + 1, r);
for (auto a : left) {
for (auto b : right) {
TreeNode* root = new TreeNode(k);
root->left = a;
root->right = b;
res.push_back(root);
}
}
}
return memo[key] = res;
}
}; class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
if n == 0:
return []
from functools import lru_cache
@lru_cache(None)
def build(l: int, r: int):
if l > r:
return (None,)
res = []
for k in range(l, r + 1):
left = build(l, k - 1)
right = build(k + 1, r)
for a in left:
for b in right:
root = TreeNode(k)
root.left = a
root.right = b
res.append(root)
return tuple(res)
return list(build(1, n))var generateTrees = function(n) {
if (n === 0) return [];
const memo = new Map();
const build = (l, r) => {
const key = `${l},${r}`;
if (memo.has(key)) return memo.get(key);
const res = [];
if (l > r) {
res.push(null);
memo.set(key, res);
return res;
}
for (let k = l; k <= r; k++) {
const left = build(l, k - 1);
const right = build(k + 1, r);
for (const a of left) {
for (const b of right) {
const root = new TreeNode(k);
root.left = a;
root.right = b;
res.push(root);
}
}
}
memo.set(key, res);
return res;
};
return build(1, n);
};
Comments