NeetCode #448LC-95MediumTrees
← Back to All Problems#448 · #95 · Unique Binary Search Trees II(不同的二叉搜索树 II)
📌 Problem Statement & Constraints
Given an integer
n, return all structurally unique binary search trees that store the values 1..n. Return the roots in any order. Constraints: 1 <= n <= 8.💡 Core Algorithmic Approaches
- Recursively build all trees over a value range
[lo, hi]. - For each candidate root value
v, combine every left tree over[lo, v-1]with every right tree over[v+1, hi]. - The base case
lo > hireturns a singleNone, representing an empty subtree. - The total output is the Catalan number, which is why
nis capped at 8.
💻 Benchmark Python3 Implementation
class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def build(lo: int, hi: int) -> List[Optional[TreeNode]]:
if lo > hi:
return [None] # one empty subtree
res = []
for v in range(lo, hi + 1): # v is the root value
for l in build(lo, v - 1):
for r in build(v + 1, hi):
res.append(TreeNode(v, l, r))
return res
return build(1, n) if n else []
# Memoised variant: reuse the trees for each (lo, hi) range
class Solution2:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
from functools import lru_cache
@lru_cache(maxsize=None)
def build(lo: int, hi: int):
if lo > hi:
return (None,)
res = []
for v in range(lo, hi + 1):
for l in build(lo, v - 1):
for r in build(v + 1, hi):
res.append(TreeNode(v, l, r))
return tuple(res)
return list(build(1, n)) if n else []⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * Catalan(n)): each generated tree requires O(n) node creations.
💾 Space Complexity
O(Catalan(n)) for the output, plus O(n) recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Returning
[]for the empty range instead of[None]: then no tree would ever be built, since the loops iterate over the child lists. - Reusing the same subtree objects across different trees: the memoised variant shares nodes, which mutates shared structure if the caller modifies the trees -- acceptable for this problem but worth noting.
- Trying to deduplicate structurally identical trees: distinct root values always give distinct BSTs, so no deduplication is needed.
- Using a value range based on 0: the values are
1..n.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.