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
Naive Way: Since it is associated with its previous question. I'll bring the code in unique-binary-search-trees for reference.
public class Solution {
public int numTrees(int n) {
// base case
if(n <= 1){return 1;}
// recursion
int sum = 0;
for(int i = 1;i <= n;i++)
sum += numTrees(i-1-0) * numTrees(n-i);
return sum;
}
}
The code cannot be inherited since it demand us to return the structure itself instead of the number of the structure. But the idea can be inherited.
Use each number i as root node, then the left branch will be what's less than i, the right branch will be what's larger than i. For left branch and right branch, we can do the same trick. But this time we need to provide both boundary for the range.
This solution needs O(2^n) run time and space because of the scale of the output.
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; left = null; right = null; }
* }
*/
public class Solution {
public List<TreeNode> generateTrees(int n) {
return generateTree(1,n+1);
}
private List<TreeNode> generateTree(int min, int max){
List<TreeNode> list = new ArrayList<TreeNode>();
// base case
if(min >= max){
TreeNode node = null;
list.add(node);
}
// general case
for(int i = min;i < max;i++){
List<TreeNode> left = generateTree(min,i);
List<TreeNode> right = generateTree(i+1,max);
for(int p = 0;p < left.size();p++){
for(int q = 0;q < right.size();q++){
TreeNode root = new TreeNode(i);
root.left = left.get(p);
root.right = right.get(q);
list.add(root);
}
}
}
return list;
}
}
