Question
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Stats
| Frequency | 1 |
| Difficulty | 4 |
| Adjusted Difficulty | 3 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is a question with standard solution.
It looks like difficult, but actually the code is very short.
Solution
This is my previous solution. Everyone in blogs are having same solution. I mean, every single one of them, one example.
Code
public ArrayList<TreeNode> generateTrees(int n) {
return construct(0, n);
}
ArrayList<TreeNode> construct(int base, int n) {
ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
if (n == 0) ans.add(null);
for (int cur = 1; cur <= n; cur++)
for (TreeNode l : construct(base, cur - 1))
for (TreeNode r : construct(base + cur, n - cur)) {
TreeNode root = new TreeNode(base + cur);
root.left = l;
root.right = r;
ans.add(root);
}
return ans;
}