# 95. Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
# Solution
Approach 1: Recursion with brute force. Make sure to generate a new tree each time so that the trees don't get modified.
Approach 2: DP based on n with value offset.
# Code (Python)
Approach 1:
class Solution:
def generateTrees(self, n: 'int') -> 'List[TreeNode]':
if n == 0:
return []
return self._generate(1, n)
def _generate(self, lo, hi):
if lo > hi:
return [None]
if lo == hi:
return [TreeNode(lo)]
result = []
for root_val in range(lo, hi + 1):
for left_tree in self._generate(lo, root_val - 1):
for right_tree in self._generate(root_val + 1, hi):
root = TreeNode(root_val)
root.left = left_tree
root.right = right_tree
result.append(root)
return result
Approach 2:
# Code (C++)
Approach 1:
// Recursion.
class Solution {
private:
vector<TreeNode*> doGenerateTrees(int head, int tail) {
vector<TreeNode*> trees;
if (head > tail)
{
trees.push_back(NULL);
}
for (int i = head; i <= tail; ++i)
{
vector<TreeNode*> leftSet = doGenerateTrees(head, i - 1);
vector<TreeNode*> rightSet = doGenerateTrees(i + 1, tail);
for (int j = 0; j < leftSet.size(); ++j)
{
for (int k = 0; k < rightSet.size(); ++k)
{
TreeNode *node = new TreeNode(i);
node->left = leftSet[j];
node->right = rightSet[k];
trees.push_back(node);
}
}
}
return trees;
}
public:
vector<TreeNode*> generateTrees(int n) {
if (n == 0)
return vector<TreeNode*>();
return doGenerateTrees(1, n);
}
};
Approach 2:
// DP based on n with value offset.
class Solution {
private:
// Trees with the same size are structurally the same.
// Just need to add the offset for each nodes's value.
TreeNode* cloneTree(TreeNode *root, int offset) {
if (root == NULL)
return NULL;
TreeNode *node = new TreeNode(root->val + offset);
node->left = cloneTree(root->left, offset);
node->right = cloneTree(root->right, offset);
return node;
}
public:
vector<TreeNode*> generateTrees(int n) {
if (n == 0)
return vector<TreeNode*>();
vector<TreeNode*> treeMap[n+1];
treeMap[0].push_back(NULL);
for (int len = 1; len <= n; ++len)
{
for (int root = 1; root <= len; ++root)
{
int leftLen = root - 1;
int rightLen = len - root;
for (int leftRoot = 0; leftRoot < treeMap[leftLen].size(); ++leftRoot)
{
for (int rightRoot = 0; rightRoot < treeMap[rightLen].size(); ++rightRoot)
{
TreeNode *node = new TreeNode(root);
node->left = cloneTree(treeMap[leftLen][leftRoot], 0);
node->right = cloneTree(treeMap[rightLen][rightRoot], root);
treeMap[len].push_back(node);
}
}
}
}
return treeMap[n];
}
};